﻿#ifndef __automata_adfhaiofh_fh823hasguj45482934__
#define __automata_adfhaiofh_fh823hasguj45482934__
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdint.h>
/*
项目约定：
- 1 C++ 03 标准
- 2 尽可能少的依赖 STL等等C++的标准库
- 3 暴露在外的接口命名均为小写字母开头的驼峰式命名法
- 4 内部实现命名相对自由
- 5 内存分配失败后直接 abort()
- 6 所有的类不会抛出异常，仅仅使用C风格的错误码
- 7 所有的非POD的类均支持拷贝构造，拷贝赋值与move的成员函数
- 8 所有的模板与容器均在 hyperlex 命名空间下，它的使用者必须显式使用 hyperlex:: 前缀
	不得使用 using namespace hyperlex;因为这些模板与容器一定与 STL 等标准库冲突
	这些模板的功能与接口与 STL 常常不同，所以仅仅用于本库内部，用户直接使用于自身代码库风险较高。
- 9 所有的“平凡析构”类型默认不可以被标记为可位搬迁的类型
- 10 项目不使用任何static类型数据，也没有任何的线程锁。项目内没有任何的全局变量，不显式的创造多线程
- 11 每一个手册上暴露在外的接口合法供用户使用的接口都可以视为某种原语，线程安全。
	用户可以在多线程中使用这些原语，但必须保证每一个原语的调用是原子的。
	例如：用户可以在多个线程中同时调用 dictionary::search()，但不可以在一个线程中调用 dictionary::search() 的同时
	在另一个线程中调用 dictionary::insert()。
- 12 显式move完成后的src对象等价于被析构后的对象，不需要再次析构。所有非平凡析构的类均提供显式move成员函数。
- 13 对变量 / 函数 / 属性用小驼峰，对类 / 实体用大驼峰 不强制如此，推荐使用
*/
/*
头文件结构
namespace hyperlex 00:
	closedInterval
namespace hyperlex 01:
	traits
namespace hyperlex 02:
	vector
	array
	buffer
namespace hyperlex 03:
	arena
*/
namespace hyperlex
{
	// 机器字长的有符号整数
#if defined(INTPTR_MAX)
	typedef intptr_t sint;
#else
	typedef ptrdiff_t sint; // C++03 兜底：与指针差同宽，通常等同字长
#endif

	// 可选：编译期校验（失败会报负数组大小）
	typedef char _hx_check_sint_is_word[(sizeof(sint) == sizeof(void*)) ? 1 : -1];

	struct closedInterval
	{
		int upper;
		int lower;
		inline bool legal(void) const
		{
			return upper >= lower && lower >= 0;
		}
		inline bool in(const char ele) const
		{
			return (int)ele >= lower && (int)ele <= upper;
		}
		inline bool in(const int ele) const
		{
			return ele >= lower && ele <= upper;
		}
		inline size_t length(void) const
		{
			return (size_t)upper - (size_t)lower + 1;
		}
		inline bool operator==(const closedInterval& in) const
		{
			return upper == in.upper && lower == in.lower;
		}
		inline bool operator!=(const closedInterval& in) const
		{
			return !(upper == in.upper && lower == in.lower);
		}
		inline bool intersect(const closedInterval& in) const
		{
			return !(upper < in.lower || lower > in.upper);
		}
		// 排序规则（字典序 / 严格弱序）
		// 按 pair(lower, upper) 升序排列：
		// 1) 先比较 lower，lower 小者更小；
		// 2) 若 lower 相等，再比较 upper，upper 小者更小。
		// 等价于：std::tie(lower, upper) < std::tie(in.lower, in.upper)
		// 说明：该顺序与 operator<= / operator> / operator>= 的实现保持一致，
		// 可安全用于 std::sort / std::set / std::map 等有序容器与算法。
		inline bool operator<(const closedInterval& in) const
		{
			if (lower != in.lower) return lower < in.lower;
			return upper < in.upper;
		}
		inline bool operator<=(const closedInterval& in) const
		{
			if (lower != in.lower) return lower < in.lower;
			return upper <= in.upper;
		}
		inline bool operator>(const closedInterval& in) const
		{
			if (lower != in.lower) return lower > in.lower;
			return upper > in.upper;
		}
		inline bool operator>=(const closedInterval& in) const
		{
			if (lower != in.lower) return lower > in.lower;
			return upper >= in.upper;
		}
		// 交集（cap）：返回 a∩b；若无交集则返回项目约定的“空区间”[0, -1]
		inline static closedInterval cap(const closedInterval& a, const closedInterval& b)
		{
			closedInterval result;
			// 交集下界取较大者，上界取较小者（闭区间）
			result.lower = (a.lower > b.lower) ? a.lower : b.lower;
			result.upper = (a.upper < b.upper) ? a.upper : b.upper;

			// 若上界 < 下界，则两区间不相交，返回空区间编码 [0, -1]
			// 注：legal() 也要求 lower >= 0，这里选择约定统一的空区间表示。
			if (!result.legal()) {
				result.lower = 0;
				result.upper = -1;
			}
			return result;
		}

		// 并集（cup）：返回能覆盖 a 与 b 的最小闭区间（凸包）
		// 若 a、b 不相交，这不是严格集合并（严格并应为两个区间）；
		// 本实现按“包围区间”使用场景设计。
		inline static closedInterval cup(const closedInterval& a, const closedInterval& b)
		{
			closedInterval result;
			// 并集的包围区间：下界取较小者，上界取较大者
			result.lower = (a.lower < b.lower) ? a.lower : b.lower;
			result.upper = (a.upper > b.upper) ? a.upper : b.upper;
			return result;
		}
	};
	struct iteratorState
	{
		size_t site;
		int state;
	};
	class StringPool;
	class FilePath;
	class charBuffer;
}
namespace hyperlex
{
	/* ================= forward decl ================= */

	template<class T> class vector;
	template<class T> class array;
	template<class T> class buffer;

	/* ==== 新增：为后面 traits 区里的偏特化补充前置声明 ==== */
	template<class T> struct bitreeNode;
	template<class T> struct gtreevNode;
	template<class T> class bitree;
	template<class T> class gtreev;
}
namespace hyperlex
{
	/* ================= forward decl ================= */

	template<class T> class vector;
	template<class T> class array;
	template<class T> class buffer;

	

	/* ================= traits ================= */
	template<class T> struct is_bitwise_relocatable { enum { value = 0 }; };
	template<class T> struct is_trivially_destructible_like { enum { value = 0 }; };
	//template<class T> struct need_explicit_move { enum { value = 0 }; };
	// 2) 用 SFINAE 实现主 traits 的检测（保留你已有的其它专用化不变）
	template<class T> struct need_explicit_move {
	private:
		typedef char yes; 
		struct no { char _[2]; };
		template<class U> static yes probe(typename U::_hx_need_explicit_move_tag*);
		template<class U> static no  probe(...);
	public:
		enum { value = sizeof(probe<T>(0)) == sizeof(yes) ? 1 : 0 };
	};

	/* 基础类型与指针：位可重定位 + 平凡析构 */
	template<> struct is_bitwise_relocatable<bool> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<int> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<unsigned int> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<long> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<unsigned long> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<long long> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<unsigned long long> { enum { value = 1 }; };
	//template<> struct is_bitwise_relocatable<size_t> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<char> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<unsigned char> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<float> { enum { value = 1 }; };
	template<> struct is_bitwise_relocatable<double> { enum { value = 1 }; };
	template<class T> struct is_bitwise_relocatable<T*> { enum { value = 1 }; };

	template<> struct is_trivially_destructible_like<bool> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<int> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<unsigned int> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<long> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<unsigned long> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<long long> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<unsigned long long> { enum { value = 1 }; };
	//template<> struct is_trivially_destructible_like<size_t> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<char> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<unsigned char> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<float> { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<double> { enum { value = 1 }; };
	template<class T> struct is_trivially_destructible_like<T*> { enum { value = 1 }; };

	/* 扩展：让带顶层 cv 的指针也视为可位搬迁 */
	template<class T> struct is_bitwise_relocatable<T* const> { enum { value = is_bitwise_relocatable<T*>::value }; };
	template<class T> struct is_bitwise_relocatable<T* volatile> { enum { value = is_bitwise_relocatable<T*>::value }; };
	template<class T> struct is_bitwise_relocatable<T* const volatile> { enum { value = is_bitwise_relocatable<T*>::value }; };

	template<class T> struct is_trivially_destructible_like<T* const> { enum { value = is_trivially_destructible_like<T*>::value }; };
	template<class T> struct is_trivially_destructible_like<T* volatile> { enum { value = is_trivially_destructible_like<T*>::value }; };
	template<class T> struct is_trivially_destructible_like<T* const volatile> { enum { value = is_trivially_destructible_like<T*>::value }; };

	/*扩展：自定义类型的位搬迁性质与平凡析构*/
	template<> struct is_bitwise_relocatable<closedInterval > { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like<closedInterval > { enum { value = 1 }; };

	/* 递归：vector<E> 仅当 E 也可位搬迁 */
	template<class E> struct is_bitwise_relocatable< vector<E> > {
		//enum { value = is_bitwise_relocatable<E>::value };
		enum { value = 0 };//为了安全起见，暂时关闭 vector 的位搬迁优化
	};
	template<class E> struct is_trivially_destructible_like< vector<E> > {
		enum { value = 0 }; /* 自身有非平凡析构逻辑，保守为 0 */
	};
	template<class E> struct need_explicit_move< vector<E> > { enum { value = 1 }; };

	template<class E> struct is_bitwise_relocatable< array<E> > { enum { value = 0 }; };
	template<class E> struct is_trivially_destructible_like< array<E> > { enum { value = 0 }; };
	template<class E> struct need_explicit_move< array<E> > { enum { value = 1 }; };

	template<class E> struct is_bitwise_relocatable< buffer<E> > { enum { value = 0 }; };
	template<class E> struct is_trivially_destructible_like< buffer<E> > { enum { value = 0 }; };
	template<class E> struct need_explicit_move< buffer<E> > { enum { value = 1 }; };

	// ===== bitreeNode 的 traits：放在同命名空间内即可 =====
	// ===== bitreeNode 的 traits：递归定义 =====
	template<class E> struct need_explicit_move< bitreeNode<E> > { enum { value = need_explicit_move<E>::value }; };
	template<class E> struct is_trivially_destructible_like< bitreeNode<E> > { enum { value = is_trivially_destructible_like<E>::value }; };
	template<class E> struct is_bitwise_relocatable< bitreeNode<E> > { enum { value = is_bitwise_relocatable<E>::value }; };

	// 显式 move 支持：递归到节点与容器本身
	// gtreevNode 显式需要 move：包含 vector<size_t> children
	template<class E> struct need_explicit_move< bitree<E> > { enum { value = 1 }; };
	template<class E> struct need_explicit_move< gtreevNode<E> > { enum { value = 1 }; };
	template<class E> struct need_explicit_move< gtreev<E> > { enum { value = 1 }; };
	// 如确实需要把 arena<T> 当值类型放进容器再启用：
	// template<class E> struct need_explicit_move< arena<E> > { enum { value = 1 }; };

	template<> struct is_bitwise_relocatable<charBuffer> { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like<charBuffer> { enum { value = 0 }; };
	template<> struct need_explicit_move<charBuffer> { enum { value = 1 }; };


	//template<class E> struct need_explicit_move< gtreevNode<E> > { enum { value = need_explicit_move<E>::value }; };

	/* ============== move 派发（无 if 常量分支） ============== */
	template<class T, bool NeedMove> struct move_assign;
	template<class T>
	struct move_assign<T, true> {
		static void apply(T& dst, T& src) { dst.move(src); }
	};
	template<class T>
	struct move_assign<T, false> {
		static void apply(T& dst, T& src) { dst = src; }
	};
} 
namespace hyperlex
{
	/* ============== vector ================== */
	template <class T> class vector
	{
	protected:
		size_t Count;
		size_t Capacity;
		T* content;

		enum { use_realloc = is_bitwise_relocatable<T>::value };

		inline void destroy_range(size_t a, size_t b) {
			if (is_trivially_destructible_like<T>::value) return;
			if (!content) return;
			while (a < b) {
				(content + a)->~T();
				++a;
			}
		}
		inline void deallocate() {
			if (!content) return;
			free(content); /* 非位搬迁路径也使用 malloc/free 统一 */
			content = NULL;
		}
		inline void grow(size_t newCap) {
			if (newCap <= Capacity) return;
			if (use_realloc) {
				T* p = (T*)realloc(content, newCap * sizeof(T));
				if (!p) ::abort();
				content = p;
				Capacity = newCap;
				return;
			}
			// 非位搬迁：新块 + (move or copy) + 析构旧
			T* newBuf = (T*)malloc(newCap * sizeof(T));
			if (!newBuf) ::abort();

			if (need_explicit_move<T>::value) {
				// 利用显式 move：减少深拷成本
				for (size_t i = 0; i < Count; ++i) {
					new (newBuf + i) T(); // 占位
					move_assign<T, need_explicit_move<T>::value>::apply(newBuf[i], content[i]);
				}
			}
			else {
				// 原拷贝路径
				for (size_t i = 0; i < Count; ++i) {
					new (newBuf + i) T(content[i]);
				}
				destroy_range(0, Count);
			}
			
			free(content);
			content = newBuf;
			Capacity = newCap;
		}
		inline void ensure_capacity_for(size_t add) {
			size_t need = Count + add;
			if (need <= Capacity) return;
			size_t nc = Capacity + Capacity / 4 + 8;
			if (nc < need) nc = need;
			grow(nc);
		}
		// 交换下标 i 与 j 的元素（move-aware）
		inline void swapItem(size_t i, size_t j) {
			if (i == j) return;
			T tmp; /* 依赖项目约定：非 POD 均提供默认构造与 move */
			move_assign<T, need_explicit_move<T>::value>::apply(tmp, content[i]);
			move_assign<T, need_explicit_move<T>::value>::apply(content[i], content[j]);
			move_assign<T, need_explicit_move<T>::value>::apply(content[j], tmp);
		}
	public:
		vector() :Count(0), Capacity(0), content(NULL) {}
		/* 拷贝构造 */
		vector(const vector& other) :Count(0), Capacity(0), content(NULL) {
			if (other.Count == 0) return;
			size_t n = other.Count;
			content = (T*)malloc(n * sizeof(T));
			if (!content) ::abort();
			for (size_t i = 0; i < n; ++i)
				new (content + i) T(other.content[i]);
			Count = Capacity = n;
		}
		~vector() {
			destroy_range(0, Count);
			deallocate();
			Capacity = 0;
			Count = 0;
		}
		/* 拷贝赋值 */
		vector& operator=(const vector& other) {
			if (this == &other) return *this;
			/* 先销毁本对象数据 */
			destroy_range(0, Count);
			if (other.Count > Capacity) {
				free(content);
				content = (T*)malloc(other.Count * sizeof(T));
				if (!content && other.Count) ::abort();
				Capacity = other.Count;
			}
			for (size_t i = 0; i < other.Count; ++i)
				new (content + i) T(other.content[i]);
			Count = other.Count;
			return *this;
		}
		// 位置：class vector<T> public: 内（例如拷贝赋值函数后面增加）
		/* 显式移动：C++03 风格，供 move_assign 调度使用 */
		void move(vector& src)
		{
			if (&src == this) return;
			// 释放当前资源
			destroy_range(0, Count);
			free(content);

			// 窃取
			content = src.content;
			Count = src.Count;
			Capacity = src.Capacity;

			// 置空源
			src.content = NULL;
			src.Count = 0;
			src.Capacity = 0;
		}

		// 在 class vector<T> public: 内合适位置追加
		inline size_t size() const { return count(); }
		inline void resize(size_t n) { recount(n); }

		inline size_t count() const { return Count; }
		inline size_t capacity() const { return Capacity; }

		inline const T* ptr() const { return content; }
		inline T* ptr() { return content; }
		inline const T* ptr(size_t off) const { return content + off; }
		inline T* ptr(size_t off) { return content + off; }

		inline const T& operator[](size_t i) const { return content[i]; }
		inline T& operator[](size_t i) { return content[i]; }

		inline void clear(void) {
			destroy_range(0, Count);
			Count = 0;
		}

		// 在 class vector<T> public: 区域内添加
		void reserve(size_t n) {
			if (n > Capacity) grow(n);
		}
		// 可选：保留旧名 recapacity -> 行为变成 reserve
		void recapacity(size_t NewSize) {
			if (NewSize > Capacity) grow(NewSize);
			if (NewSize < Count) {           // 仅截断，不收缩容量
				destroy_range(NewSize, Count);
				Count = NewSize;
			}
		}

		void recount(size_t NewCount) {
			if (NewCount > Capacity) grow(NewCount);
			if (NewCount < Count) {
				destroy_range(NewCount, Count);
				Count = NewCount;
				return;
			}
			if (NewCount > Count) {
				for (size_t i = Count; i < NewCount; ++i)
					new (content + i) T();
				Count = NewCount;
			}
		}

		size_t append(void) {
			ensure_capacity_for(1);
			new (content + Count) T();
			return Count++;
		}
		void append(const T& element) {
			ensure_capacity_for(1);
			new (content + Count) T(element);
			++Count;
		}
		void append(const vector& source) {
			if (!source.Count) return;
			ensure_capacity_for(source.Count);
			size_t base = Count;
			for (size_t i = 0; i < source.Count; ++i)
				new (content + base + i) T(source.content[i]);
			Count += source.Count;
		}
		/* 移动版单元素追加：优先尝试显式 move，否则退化为拷贝
   返回后 element 处于已移动或原值状态（取决于 need_explicit_move<T>） */
   /* 单元素追加（破坏性：element 被视为已 move 或保持原值；不析构 element） */
		void appendMove(T& element) {
			ensure_capacity_for(1);
			new (content + Count) T(); // 占位
			// move_assign 根据 need_explicit_move 常量分派：有 move() 用 move，否则用赋值
			move_assign<T, need_explicit_move<T>::value>::apply(content[Count], element);
			++Count;
		}

		/* 破坏性移动追加：将 source 全部元素搬到尾部；不显式析构 source 中元素，仅把 Count 置 0 */
		void appendMove(vector& source) {
			if (&source == this || source.Count == 0) return;

			// 目标为空，直接整体窃取（O(1)）
			if (Count == 0) {
				move(source); // 已把 source 置空
				return;
			}

			ensure_capacity_for(source.Count);
			size_t base = Count;

			// 逐元素占位 + move/赋值
			for (size_t i = 0; i < source.Count; ++i) {
				new (content + base + i) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[base + i], source.content[i]);
			}

			Count += source.Count;
			// 破坏性：source 清空（其缓冲里对象均已 move，按约定视为已析构，不再手动析构）
			source.Count = 0;
		}

		/* 批量插入（非破坏：elements 外部数组，不修改其内容，不析构任何已存在元素） */
		size_t insertMove(size_t pos, T* elements, size_t insertCount) {
			if (insertCount == 0) return (pos > Count ? Count : pos);
			if (pos > Count) pos = Count;

			ensure_capacity_for(insertCount);

			// 尾插：直接构造 + move/赋值
			if (pos == Count) {
				for (size_t k = 0; k < insertCount; ++k) {
					new (content + Count + k) T();
					move_assign<T, need_explicit_move<T>::value>::apply(content[Count + k], elements[k]);
				}
				Count += insertCount;
				return pos;
			}

			// 右移尾段：[pos, Count) -> [pos+insertCount, Count+insertCount)
			// 从尾到头，避免覆盖
			for (size_t i = 0; i < Count - pos; ++i) {
				size_t src = Count - 1 - i;
				size_t dst = src + insertCount;
				new (content + dst) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[dst], content[src]);
				// 不析构 src（移动后 src 为“已析构状态”或保留副本，统一在容器析构时处理）
			}

			// 放入新元素
			for (size_t k = 0; k < insertCount; ++k) {
				new (content + pos + k) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[pos + k], elements[k]);
			}

			Count += insertCount;
			return pos;
		}

		/* 破坏性插入：把 source 全部元素插入到 pos；不析构 source 中元素，仅置 source.Count=0 */
		size_t insertMove(size_t pos, vector& source) {
			if (&source == this) return (pos > Count ? Count : pos);
			size_t n = source.Count;
			if (n == 0) return (pos > Count ? Count : pos);
			if (pos > Count) pos = Count;

			// 尾插等价 appendMove
			if (pos == Count) {
				appendMove(source);
				return pos;
			}

			ensure_capacity_for(n);

			// 右移尾段
			for (size_t i = 0; i < Count - pos; ++i) {
				size_t src = Count - 1 - i;
				size_t dst = src + n;
				new (content + dst) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[dst], content[src]);
			}

			// 填入 source 的元素（破坏性 move）
			for (size_t i = 0; i < n; ++i) {
				new (content + pos + i) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[pos + i], source.content[i]);
			}

			Count += n;
			source.Count = 0;
			return pos;
		}
		/* 单元素版本（转调） */
		size_t insertMove(size_t pos, T& element) {
			return insertMove(pos, &element, 1);
		}

		void copy(const vector& source) {
			if (this == &source) return;
			clear();
			if (source.Count > Capacity) grow(source.Count);
			for (size_t i = 0; i < source.Count; ++i)
				new (content + i) T(source.content[i]);
			Count = source.Count;
		}
		size_t SearchAppend(const T& element) {
			for (size_t i = 0; i < Count; ++i)
				if (content[i] == element) return i;
			append(element);
			return Count - 1;
		}
		size_t pop(T& element) {
			if (Count == 0) return 0;
			Count -= 1;
			move_assign<T, need_explicit_move<T>::value>::apply(element, content[Count]);
			if (!is_trivially_destructible_like<T>::value)
				(content + Count)->~T();
			return Count + 1;
		}
		void pop(void) {
			if (Count == 0) return;
			Count -= 1;
			if (!is_trivially_destructible_like<T>::value)
				(content + Count)->~T();
		}
		size_t top(T& element) {
			if (Count == 0) return 0;
			element = content[Count - 1];
			return Count;
		}
		const T& top(void) const {
			assert(Count > 0 && "vector::top() called on empty vector");
			size_t idx = Count ? Count - 1 : 0;
			return content[idx];
		}
		T& top(void) {
			assert(Count > 0 && "vector::top() called on empty vector");
			size_t idx = Count ? Count - 1 : 0;
			return content[idx];
		}
		void value(const T& e) {
			for (size_t i = 0; i < Count; ++i) content[i] = e;
		}
		void swap(vector& other) {
			T* pc = other.content; other.content = content; content = pc;
			size_t v = other.Count; other.Count = Count; Count = v;
			v = other.Capacity; other.Capacity = Capacity; Capacity = v;
		}


		// —— 排序与有序性检查 ——
// 升序堆排序（非稳定，O(n log n)）
		void sortAsc() {
			if (Count < 2) return;
			const size_t n = Count;
			// 建“最大堆”
			for (size_t i = (n / 2); i > 0; --i) siftDownAsc(i - 1, n - 1);
			// 选择置尾
			for (size_t end = n - 1; end > 0; --end) {
				swapItem(0, end);
				siftDownAsc(0, end - 1);
			}
		}
		// 降序堆排序（非稳定，O(n log n)）
		void sortDesc() {
			if (Count < 2) return;
			const size_t n = Count;
			// 建“最小堆”
			for (size_t i = (n / 2); i > 0; --i) siftDownDesc(i - 1, n - 1);
			// 选择置尾
			for (size_t end = n - 1; end > 0; --end) {
				swapItem(0, end);
				siftDownDesc(0, end - 1);
			}
		}
		// 检查 [offset, Count) 是否非降序（允许相等）
		bool checkAsc(size_t offset = 0) const {
			for (size_t i = offset; i + 1 < Count; ++i) {
				// 仅用 operator>
				if (content[i] > content[i + 1]) return false;
			}
			return true;
		}
		// 检查 [offset, Count) 是否非升序（允许相等）
		bool checkDesc(size_t offset = 0) const {
			for (size_t i = offset; i + 1 < Count; ++i) {
				// 仅用 operator<
				if (content[i] < content[i + 1]) return false;
			}
			return true;
		}

		bool operator==(const vector& other) const {
			if (Count != other.Count) return false;
			for (size_t i = 0; i < Count; ++i) {
				if (!(content[i] == other.content[i])) return false;
			}
			return true;
		}
		bool operator!=(const vector& other) const {
			return !(*this == other);
		}

		// 升序版本（与现有 binarySearchIndex 相同语义）：[offset,Count) 中二分查找
		bool binarySearchIndexAsc(const T& key, size_t& pos, size_t offset = 0) const {
			if (offset > Count) offset = Count;
			size_t lo = offset;
			size_t hi = Count;
			while (lo < hi) {
				size_t mid = lo + ((hi - lo) >> 1);
				if (content[mid] < key) {
					lo = mid + 1;
				}
				else if (key < content[mid]) {
					hi = mid;
				}
				else {
					pos = mid;
					return true;
				}
			}
			pos = lo; // 插入到第一个 >= key 的位置
			return false;
		}

		// 降序版本（非增序/从大到小）：[offset,Count) 中二分查找
		// 语义：返回第一个 <= key 的位置作为插入点，保持非增序
		bool binarySearchIndexDesc(const T& key, size_t& pos, size_t offset = 0) const {
			if (offset > Count) offset = Count;
			size_t lo = offset;
			size_t hi = Count; // [lo,hi)
			while (lo < hi) {
				size_t mid = lo + ((hi - lo) >> 1);
				if (content[mid] > key) {
					// mid 比 key 大，降序下应把 key 插到右侧
					lo = mid + 1;
				}
				else if (key > content[mid]) {
					// key 比 mid 大，降序下应把 key 插到左侧
					hi = mid;
				}
				else {
					pos = mid;
					return true;
				}
			}
			pos = lo; // 插入到第一个 <= key 的位置
			return false;
		}
private:
	// 最大堆下滤：用于升序排序
	inline void siftDownAsc(size_t start, size_t end) {
		size_t root = start;
		for (;;) {
			size_t child = root * 2 + 1;
			if (child > end) break;
			size_t swapIdx = root;
			if (content[swapIdx] < content[child]) swapIdx = child;
			if (child + 1 <= end && content[swapIdx] < content[child + 1]) swapIdx = child + 1;
			if (swapIdx == root) return;
			swapItem(root, swapIdx);
			root = swapIdx;
		}
	}
	// 最小堆下滤：用于降序排序
	inline void siftDownDesc(size_t start, size_t end) {
		size_t root = start;
		for (;;) {
			size_t child = root * 2 + 1;
			if (child > end) break;
			size_t swapIdx = root;
			if (content[child] < content[swapIdx]) swapIdx = child;
			if (child + 1 <= end && content[child + 1] < content[swapIdx]) swapIdx = child + 1;
			if (swapIdx == root) return;
			swapItem(root, swapIdx);
			root = swapIdx;
		}
	}
	};

	/* ===================== array<T> 替换版 ===================== */
	template <class T> class array
	{
	protected:
		size_t Length;
		T* content;
		enum { use_realloc = is_bitwise_relocatable<T>::value };
		void destroy_range(size_t a, size_t b) {
			if (is_trivially_destructible_like<T>::value) return;
			if (!content) return;
			while (a < b) {
				(content + a)->~T();
				++a;
			}
		}
	public:
		array() :Length(0), content(NULL) {}
		/* 拷贝构造 */
		array(const array& other) :Length(0), content(NULL) {
			if (other.Length == 0) return;
			content = (T*)malloc(other.Length * sizeof(T));
			if (!content) ::abort();
			for (size_t i = 0; i < other.Length; ++i)
				new (content + i) T(other.content[i]);
			Length = other.Length;
		}
		/* 拷贝赋值 */
		array& operator=(const array& other) {
			if (this == &other) return *this;
			destroy_range(0, Length);
			if (other.Length != Length) {
				free(content);
				content = NULL;
				if (other.Length) {
					content = (T*)malloc(other.Length * sizeof(T));
					if (!content) ::abort();
				}
				Length = other.Length;
			}
			for (size_t i = 0; i < Length; ++i)
				new (content + i) T(other.content[i]);
			return *this;
		}
		/* 显式移动（供 move_assign 调用） */
		void move(array& src) {
			if (&src == this) return;
			destroy_range(0, Length);
			free(content);
			content = src.content;
			Length = src.Length;
			src.content = NULL;
			src.Length = 0;
		}
		~array() {
			destroy_range(0, Length);
			free(content);
			content = NULL;
			Length = 0;
		}

		size_t length() const { return Length; }
		size_t count() const { return Length; }
		T* ptr() { return content; }
		const T* ptr() const { return content; }
		T* ptr(size_t off) { return content + off; }
		const T* ptr(size_t off) const { return content + off; }

		T& operator[](size_t i) { return content[i]; }
		const T& operator[](size_t i) const { return content[i]; }

		/* 分配并默认构造（旧实现未构造对象，这里改为安全构造） */
		void Malloc(size_t NewSize) {
			destroy_range(0, Length);
			free(content);
			content = NULL;
			Length = 0;
			if (!NewSize) return;
			content = (T*)malloc(NewSize * sizeof(T));
			if (!content) ::abort();
			for (size_t i = 0; i < NewSize; ++i)
				new (content + i) T();
			Length = NewSize;
		}
		/* 重新分配：保留前 min(旧,新) 个元素 */
		void Realloc(size_t NewSize) {
			if (NewSize == Length) return;
			if (use_realloc) {
				size_t old = Length;
				T* p = (T*)realloc(content, NewSize * sizeof(T));
				if (!p && NewSize) ::abort();
				content = p;
				if (NewSize > old) {
					for (size_t i = old; i < NewSize; ++i)
						new (content + i) T();
				}
				else { /* 缩小销毁尾部 */
					destroy_range(NewSize, old);
				}
				Length = NewSize;
				return;
			}
			/* 安全路径 */
			T* newBuf = NULL;
			if (NewSize) {
				newBuf = (T*)malloc(NewSize * sizeof(T));
				if (!newBuf) ::abort();
				size_t toCopy = (NewSize < Length) ? NewSize : Length;
				for (size_t i = 0; i < toCopy; ++i)
					new (newBuf + i) T(content[i]);
				for (size_t i = toCopy; i < NewSize; ++i)
					new (newBuf + i) T();
			}
			destroy_range(0, Length);
			free(content);
			content = newBuf;
			Length = NewSize;
		}
		void Free() {
			destroy_range(0, Length);
			free(content);
			content = NULL;
			Length = 0;
		}
		void value(const T& e) {
			for (size_t i = 0; i < Length; ++i) content[i] = e;
		}
	};

	/* ===================== buffer<T> 替换版 ===================== */
	template <class T> class buffer
	{
	protected:
		mutable size_t Rear;
		mutable size_t Capacity;
		mutable size_t Head;
		mutable T* content;

		enum { use_realloc = is_bitwise_relocatable<T>::value };

		void destroy_range(size_t a, size_t b) {
			if (is_trivially_destructible_like<T>::value) return;
			if (!content) return;
			while (a < b) {
				(content + a)->~T();
				++a;
			}
		}
		/* 将 [Head,Rear) 前移到 0（必要时） */
		void compact_if_needed() {
			if (Head == 0) return;
			if (!content) return;
			size_t cnt = Rear - Head;
			if (!cnt) { Head = Rear = 0; return; }
			/* 非位搬迁类型：逐个移动构造 */
			if (!use_realloc) {
				for (size_t i = 0; i < cnt; ++i) {
					if (i != Head + i)
						new (content + i) T(content[Head + i]);
				}
			}
			else {
				/* 位搬迁：memmove 即可 */
				memmove(content, content + Head, cnt * sizeof(T));
			}
			/* 销毁旧位置（非平凡） */
			if (!is_trivially_destructible_like<T>::value) {
				for (size_t i = cnt; i < cnt + Head; ++i)
					(content + i)->~T();
			}
			Head = 0;
			Rear = cnt;
		}
		void ensure_capacity_for(size_t add) const {
			size_t need = Rear + add;
			if (need <= Capacity) return;
			/* 先尝试挪前空洞 */
			if (Head && (need - Head) <= Capacity) {
				compact_if_needed();
				if (Rear + add <= Capacity) return;
			}
			size_t newCap = Capacity + Capacity / 4 + 8;
			if (newCap < need) newCap = need;
			if (use_realloc && Head == 0) {
				T* p = (T*)realloc(content, newCap * sizeof(T));
				if (!p) ::abort();
				content = p;
				Capacity = newCap;
				return;
			}
			/* 安全路径：新缓冲，自 0 起复制 */
			size_t cnt = Rear - Head;
			T* newBuf = (T*)malloc(newCap * sizeof(T));
			if (!newBuf) ::abort();
			for (size_t i = 0; i < cnt; ++i)
				new (newBuf + i) T(content[Head + i]);
			destroy_range(Head, Rear);
			free(content);
			content = newBuf;
			Capacity = newCap;
			Head = 0;
			Rear = cnt;
		}
	public:
		buffer() :Rear(0), Capacity(0), Head(0), content(NULL) {}
		buffer(const buffer& other) :Rear(0), Capacity(0), Head(0), content(NULL) {
			size_t cnt = other.count();
			if (!cnt) return;
			content = (T*)malloc(cnt * sizeof(T));
			if (!content) ::abort();
			for (size_t i = 0; i < cnt; ++i)
				new (content + i) T(other.content[other.Head + i]);
			Capacity = cnt;
			Head = 0;
			Rear = cnt;
		}
		buffer& operator=(const buffer& other) {
			if (this == &other) return *this;
			destroy_range(Head, Rear);
			Head = Rear = 0;
			if (other.count() > Capacity) {
				free(content);
				content = (T*)malloc(other.count() * sizeof(T));
				if (!content && other.count()) ::abort();
				Capacity = other.count();
			}
			size_t cnt = other.count();
			for (size_t i = 0; i < cnt; ++i)
				new (content + i) T(other.content[other.Head + i]);
			Head = 0;
			Rear = cnt;
			return *this;
		}
		void move(buffer& src) {
			if (&src == this) return;
			destroy_range(Head, Rear);
			free(content);
			content = src.content;
			Rear = src.Rear;
			Capacity = src.Capacity;
			Head = src.Head;
			src.content = NULL;
			src.Head = src.Rear = src.Capacity = 0;
		}
		~buffer() {
			destroy_range(Head, Rear);
			free(content);
			content = NULL;
			Head = Rear = Capacity = 0;
		}

		void clear() {
			destroy_range(Head, Rear);
			Head = Rear = 0;
		}

		/* 追加另一个 buffer (按顺序复制) */
		void append(const buffer& other) {
			size_t cnt = other.count();
			if (!cnt) return;
			ensure_capacity_for(cnt);
			for (size_t i = 0; i < cnt; ++i)
				new (content + Rear + i) T(other.content[other.Head + i]);
			Rear += cnt;
		}

		size_t append(const T& e) {
			ensure_capacity_for(1);
			new (content + Rear) T(e);
			return Rear++;
		}

		/* 移动版单元素追加：若类型声明需要显式 move 则调用 move_assign，否则退化为拷贝 */
		void appendMove(T& element) {
			ensure_capacity_for(1);
			if (need_explicit_move<T>::value) {
				new (content + Rear) T();
				move_assign<T, need_explicit_move<T>::value>::apply(content[Rear], element);
			}
			else {
				new (content + Rear) T(element);
			}
			++Rear;
		}

		/* 破坏性移动追加：把 source 的全部有效元素 [source.Head, source.Rear) 移到当前尾部
		   之后 source 清空 (Head=Rear=0)。source 与 this 相同则无操作 */
		void appendMove(buffer& source) {
			if (&source == this) return;
			size_t scount = source.count();
			if (scount == 0) return;

			/* 目标当前为空：直接偷整块（O(1）） */
			if (Rear == Head) {
				move(source);
				/* 如果希望偷来后紧凑，可启用：
				   // if (Head != 0) compact_if_needed();
				*/
				return;
			}

			ensure_capacity_for(scount);
			size_t base = Rear;

			if (is_bitwise_relocatable<T>::value) {
				/* 位可搬迁：直接字节复制 */
				memcpy(content + base,
					source.content + source.Head,
					scount * sizeof(T));
				if (!is_trivially_destructible_like<T>::value) {
					source.destroy_range(source.Head, source.Rear);
				}
				Rear += scount;
				source.Head = source.Rear = 0;
				return;
			}

			/* 非位搬迁：逐元素构造 + 析构 */
			for (size_t i = 0; i < scount; ++i) {
				T* src_slot = source.content + source.Head + i;
				new (content + base + i) T(*src_slot); // 当前仅有拷贝构造
				if (!is_trivially_destructible_like<T>::value)
					src_slot->~T();
			}
			Rear += scount;
			source.Head = source.Rear = 0;
		}

		/* 与旧接口兼容：expand 仅预留一个槽并默认构造 */
		size_t expand() {
			ensure_capacity_for(1);
			new (content + Rear) T();
			return Rear++;
		}
		void expand(const size_t L) {
			if (!L) return;
			ensure_capacity_for(L);
			for (size_t i = 0; i < L; ++i)
				new (content + Rear + i) T();
			Rear += L;
		}
		bool dequeue(T& out) {
			if (Head >= Rear) return false;
			move_assign<T, need_explicit_move<T>::value>::apply(out, content[Head]);
			if (!is_trivially_destructible_like<T>::value)
				(content + Head)->~T();
			++Head;
			if (Head == Rear) { Head = Rear = 0; } /* 为空复位 */
			return true;
		}
		bool backspace(T& in) {
			if (Head == 0) return false;
			--Head;
			/* 位置 Head 已被视为空位 */
			new (content + Head) T(in);
			return true;
		}
		bool backspace(buffer& in) {
			size_t LL = in.count();
			if (LL > Head) return false;
			/* 先把 in 中元素搬到前面空洞 */
			for (size_t i = 0; i < LL; ++i) {
				new (content + Head - LL + i) T(in.content[in.Head + i]);
			}
			Head -= LL;
			in.clear();
			return true;
		}

		T* ptr() { return content + Head; }
		const T* ptr() const { return content + Head; }
		size_t count() const { return Rear - Head; }
		size_t rear() const { return Rear; }
		size_t capacity() const { return Capacity; }
		size_t head() const { return Head; }

		const T& operator[](size_t idx) const { return content[idx]; }
		inline T& operator[](size_t i) { return content[i]; }
	};
}

/* ====================== Arena (方案B：vector<size_t> 空闲栈) ====================== */
namespace hyperlex
{
	template<class T>
	class arena
	{
	public:
		typedef T value_type;
		enum { npos_enum = -1 };
		/* blockExp 是每块大小的对数，但是愚蠢的gpt将它命名成了指数，上限是20 超过后直接崩溃 */
		arena(size_t blockExp = 8)
			:blockExp_(blockExp),
			blockSize_((size_t)1 << blockExp),
			blockMask_(blockSize_ - 1),
			size_(0),
			usedInLast_(0),
			liveCount_(0)
		{
			if (blockExp_ > 20) ::abort();
		}
		~arena() { clear(); }
		
		/* 拷贝构造：深拷贝块与存活对象，保持全局索引不变 */
		arena(const arena& other)
			: blockExp_(other.blockExp_)
			, blockSize_(other.blockSize_)
			, blockMask_(other.blockMask_)
			, size_(other.size_)
			, usedInLast_(other.usedInLast_)
			, liveCount_(other.liveCount_)
		{
			/* 1) 复制块布局并分配内存块（未构造对象） */
			size_t bc = other.Blocks_.count();
			for (size_t b = 0; b < bc; ++b) {
				T* mem = (T*)malloc(blockSize_ * sizeof(T));
				if (!mem) ::abort();
				Blocks_.append(mem);
			}

			/* 2) 复制 alive_ 与 freeIdx_ 元数据 */
			alive_ = other.alive_;
			freeIdx_ = other.freeIdx_;

			/* 3) 按 alive_ 构造存活对象，保持相同全局索引 */
			size_t n = size_ < alive_.count() ? size_ : alive_.count();
			for (size_t i = 0; i < n; ++i) {
				if (!alive_[i]) continue;
				T* dst = raw_slot(i);
				new (dst) T(other[i]);
			}
		}

		/* 拷贝赋值：清空自身后，深拷贝 other 到当前实例 */
		arena<T>& operator=(const arena& other)
		{
			if (this == &other) return *this;

			/* 0) 清理自身（析构存活 + 释放块） */
			clear();

			/* 1) 复制基本参数 */
			blockExp_ = other.blockExp_;
			blockSize_ = other.blockSize_;
			blockMask_ = other.blockMask_;
			size_ = other.size_;
			usedInLast_ = other.usedInLast_;
			liveCount_ = other.liveCount_;

			/* 2) 复制块布局并分配内存块（未构造对象） */
			size_t bc = other.Blocks_.count();
			for (size_t b = 0; b < bc; ++b) {
				T* mem = (T*)malloc(blockSize_ * sizeof(T));
				if (!mem) ::abort();
				Blocks_.append(mem);
			}

			/* 3) 复制 alive_ 与 freeIdx_ 元数据 */
			alive_ = other.alive_;
			freeIdx_ = other.freeIdx_;

			/* 4) 按 alive_ 构造存活对象，保持相同全局索引 */
			size_t n = size_ < alive_.count() ? size_ : alive_.count();
			for (size_t i = 0; i < n; ++i) {
				if (!alive_[i]) continue;
				T* dst = raw_slot(i);
				new (dst) T(other[i]);
			}
			return *this;
		}

		/* 显式移动（C++03 风格）：窃取所有资源，src 置为空 Arena */
		void move(arena& src)
		{
			if (&src == this) return;

			/* 0) 释放当前资源 */
			clear();

			/* 1) 窃取底层容器（O(1)） */
			Blocks_.move(src.Blocks_);
			freeIdx_.move(src.freeIdx_);
			alive_.move(src.alive_);

			/* 2) 复制标量状态 */
			blockExp_ = src.blockExp_;
			blockSize_ = src.blockSize_;
			blockMask_ = src.blockMask_;
			size_ = src.size_;
			usedInLast_ = src.usedInLast_;
			liveCount_ = src.liveCount_;

			/* 3) 将源置为有效的“空”状态（保留块参数以便后续使用） */
			src.size_ = 0;
			src.usedInLast_ = 0;
			src.liveCount_ = 0;
		}

		/* 分配一个默认构造的对象，返回全局索引 */
		size_t create()
		{
			if (freeIdx_.count() != 0)
				return reuse_slot_default();
			return bump_new_default();
		}
		/* 分配并拷贝构造 */
		size_t create(const T& v)
		{
			if (freeIdx_.count() != 0)
				return reuse_slot_copy(v);
			return bump_new_copy(v);
		}

		/* 删除（回收槽位）- 幂等：重复调用安全 */
		void erase(size_t idx)
		{
			if (idx >= size_) return;
			if (alive_.count() <= idx || !alive_[idx]) return; // 已释放，忽略
			T* slot = raw_slot(idx);
			if (!is_trivially_destructible_like<T>::value)
				slot->~T();
			alive_[idx] = (char)0;
			freeIdx_.append(idx);
			--liveCount_;
		}

		/* 获取引用（未检查是否已被 erase） */
		T& operator[](size_t idx) { return *raw_slot(idx); }
		const T& operator[](size_t idx) const { return *raw_slot(idx); }

		size_t size() const { return liveCount_; }
		size_t rawUpperBound() const { return size_; }
		size_t blockCount() const { return Blocks_.count(); }
		size_t blockSize() const { return blockSize_; }
		size_t capacitySlots() const { return Blocks_.count() * blockSize_; }
		size_t freeCount() const { return freeIdx_.count(); }

		/* 是否仍存活（O(1)） */
		bool alive(size_t idx) const
		{
			return idx < size_ && idx < alive_.count() && alive_[idx] != 0;
		}
		/* 遍历存活对象 */
		template<class F>
		void for_each_live(F f)
		{
			if (liveCount_ == 0) return;
			size_t n = size_;
			size_t m = alive_.count();
			if (m < n) n = m;
			for (size_t i = 0; i < n; ++i)
				if (alive_[i]) f(*raw_slot(i), i);
		}
		/* reset：析构存活，保留全部块与容量，索引从 0 重来 */
		void reset()
		{
			destruct_all_live();
			freeIdx_.clear();
			size_ = 0;
			usedInLast_ = 0;
			liveCount_ = 0;
			alive_.clear();
		}

		/* clear：析构存活，释放所有块与内部结构 */
		void clear()
		{
			destruct_all_live();
			for (size_t i = 0; i < Blocks_.count(); ++i) {
				free(Blocks_[i]);
				Blocks_[i] = NULL;
			}
			Blocks_.clear();
			freeIdx_.clear();
			alive_.clear();
			size_ = 0;
			usedInLast_ = 0;
			liveCount_ = 0;
		}

		void demo(FILE* fp)
		{
			fprintf(fp, "arena summary:\n");
			fprintf(fp, "  blocks        : %zu\n", Blocks_.count());
			fprintf(fp, "  blockExp      : %zu\n", blockExp_);
			fprintf(fp, "  blockSize     : %zu\n", blockSize_);
			fprintf(fp, "  capacitySlots : %zu\n", Blocks_.count() * blockSize_);
			fprintf(fp, "  size(rawUpper): %zu\n", size_);
			fprintf(fp, "  liveCount     : %zu\n", liveCount_);
			fprintf(fp, "  freeCount     : %zu\n", freeIdx_.count());
			for (size_t b = 0; b < Blocks_.count(); ++b)
				fprintf(fp, "  block[%zu] base = %p\n", b, (void*)Blocks_[b]);

			fprintf(fp, "objects:\n");
			size_t n = size_ < alive_.count() ? size_ : alive_.count();
			for (size_t idx = 0; idx < n; ++idx) {
				if (!alive_[idx]) continue;
				size_t block = idx >> blockExp_;
				size_t offset = idx & blockMask_;
				fprintf(fp, "  (%zu,%zu,%zu): ", idx, block, offset);
				raw_slot(idx)->demo(fp);
			}
		}

	private:
		/* ============ 内部状态 ============ */
		vector<T*>      Blocks_;     /* 每块指针（顺序重要：块号 == 下标） */
		vector<size_t>  freeIdx_;    /* 空闲槽索引栈（LIFO） */
		vector<char>    alive_;      /* 槽位存活标记：1=alive, 0=free */
		size_t blockExp_;            /* 每块大小的对数，但是愚蠢的gpt将它命名成了指数 */
		size_t blockSize_;
		size_t blockMask_;
		size_t size_;                /* bump 下一个新索引 */
		size_t usedInLast_;          /* 仅作统计/调试，可不依赖 */
		size_t liveCount_;           /* 当前存活对象数 */

		/* ============ 工具函数 ============ */
		inline T* block_ptr(size_t bi) const { return Blocks_[bi]; }
		inline T* raw_slot(size_t idx) const
		{
			size_t b = idx >> blockExp_;
			size_t o = idx & blockMask_;
			return block_ptr(b) + o;
		}

		void alloc_new_block()
		{
			T* mem = (T*)malloc(blockSize_ * sizeof(T));
			if (!mem) ::abort();
			Blocks_.append(mem);
			usedInLast_ = 0;
		}

		/* 计算块与偏移，保证按 idx 映射放置，避免 reset 后错位 */
		inline T* ensure_slot_for_index(size_t idx, size_t& outBlockIdx, size_t& outOffset)
		{
			outBlockIdx = idx >> blockExp_;
			outOffset = idx & blockMask_;
			while (Blocks_.count() <= outBlockIdx) alloc_new_block();
			/* 维护 usedInLast_（仅用于观察） */
			if (outBlockIdx + 1 == Blocks_.count())
				usedInLast_ = outOffset + 1;
			return Blocks_[outBlockIdx] + outOffset;
		}

		size_t bump_new_default()
		{
			size_t idx = size_;
			size_t bi, off;
			T* slot = ensure_slot_for_index(idx, bi, off);
			new (slot) T();
			if (alive_.count() <= idx) alive_.recount(idx + 1);
			alive_[idx] = (char)1;
			++size_;
			++liveCount_;
			return idx;
		}
		size_t bump_new_copy(const T& v)
		{
			size_t idx = size_;
			size_t bi, off;
			T* slot = ensure_slot_for_index(idx, bi, off);
			new (slot) T(v);
			if (alive_.count() <= idx) alive_.recount(idx + 1);
			alive_[idx] = (char)1;
			++size_;
			++liveCount_;
			return idx;
		}
		size_t reuse_slot_default()
		{
			size_t n = freeIdx_.count();
			size_t idx = freeIdx_[n - 1];
			freeIdx_.pop();
			T* slot = raw_slot(idx);
			new (slot) T();
			/* 标记存活（alive_ 总是 >= size_，但 idx 可能 < size_） */
			if (alive_.count() <= idx) alive_.recount(idx + 1);
			alive_[idx] = (char)1;
			++liveCount_;
			return idx;
		}
		size_t reuse_slot_copy(const T& v)
		{
			size_t n = freeIdx_.count();
			size_t idx = freeIdx_[n - 1];
			freeIdx_.pop();
			T* slot = raw_slot(idx);
			new (slot) T(v);
			if (alive_.count() <= idx) alive_.recount(idx + 1);
			alive_[idx] = (char)1;
			++liveCount_;
			return idx;
		}

		void destruct_all_live()
		{
			if (size_ == 0 || liveCount_ == 0) return;
			size_t n = size_ < alive_.count() ? size_ : alive_.count();
			if (!is_trivially_destructible_like<T>::value) {
				for (size_t i = 0; i < n; ++i) {
					if (!alive_[i]) continue;
					raw_slot(i)->~T();
					alive_[i] = (char)0;
				}
			}
			else {
				for (size_t i = 0; i < n; ++i) alive_[i] = (char)0;
			}
			liveCount_ = 0;
		}
	};
}/* namespace hyperlex */
/* ====================== End Arena ====================== */
/* ===================== 二叉树节点 ====================== */
namespace hyperlex
{
	/* =========== 二叉树节点：放入 arena 的元素类型 =========== */
	template<class T>
	struct bitreeNode
	{
		size_t left;
		size_t right;
		T      data;

		bitreeNode() : left((size_t)-1), right((size_t)-1), data() {}
		explicit bitreeNode(const T& v) : left((size_t)-1), right((size_t)-1), data(v) {}

		// 保留拷贝语义（不影响“析构是否平凡”）
		bitreeNode(const bitreeNode& rhs) : left(rhs.left), right(rhs.right), data(rhs.data) {}
		bitreeNode& operator=(const bitreeNode& rhs) {
			if (this != &rhs) { left = rhs.left; right = rhs.right; data = rhs.data; }
			return *this;
		}
		// 注意：不要显式定义析构函数，保持类型为“平凡析构”候选

		// 若上层容器需要 move，可按 T 的 need_explicit_move 调度
		void move(bitreeNode& src) {
			if (this == &src) return;
			left = src.left;
			right = src.right;
			move_assign<T, need_explicit_move<T>::value>::apply(data, src.data);
		}

		void demo(FILE* fp) {
			fprintf(fp, "left=%zu, right=%zu, data=", left, right);
			data.demo(fp);
		}
	};

	/* =========== 基于 arena 的二叉树（可共享 arena） =========== */
	template<class T>
	class bitree
	{
	public:
		typedef bitreeNode<T> node_type;
		static inline size_t npos() { return (size_t)-1; }

		/* 自建并拥有一个 arena（独占模式） */
		explicit bitree(size_t blockExp = 8)
			: pool_(new arena<node_type>(blockExp)), ownPool_(true), root_(npos()) {
		}
		/* 自建并拥有一个 arena（独占模式）+ 直接建根 */
		bitree(const T& rootValue, size_t blockExp = 8)
			: pool_(new arena<node_type>(blockExp)), ownPool_(true), root_(npos()) {
			make_root(rootValue);
		}
		/* 绑定外部 arena（共享模式，不拥有） */
		explicit bitree(arena<node_type>& sharedPool)
			: pool_(&sharedPool), ownPool_(false), root_(npos()) {
		}
		/* 绑定外部 arena（共享模式，不拥有）+ 直接建根 */
		bitree(const T& rootValue, arena<node_type>& sharedPool)
			: pool_(&sharedPool), ownPool_(false), root_(npos()) {
			make_root(rootValue);
		}

		/* 拷贝构造：深拷贝子树。沿用源对象的“拥有模式” */
		bitree(const bitree& other)
			: pool_(NULL), ownPool_(false), root_(npos())
		{
			if (!other.pool_) { pool_ = NULL; ownPool_ = false; root_ = npos(); return; }

			if (other.ownPool_) {
				size_t be = calc_block_exp(other.pool_->blockSize());
				pool_ = new arena<node_type>(be);
				ownPool_ = true;
			}
			else {
				pool_ = other.pool_;
				ownPool_ = false;
			}
			if (other.root_ != npos())
				root_ = clone_subtree(other.root_, *other.pool_, *pool_);
		}

		/* 拷贝赋值：保留当前对象的“拥有模式与池”，将源子树克隆到当前池 */
		bitree& operator=(const bitree& other)
		{
			if (this == &other) return *this;

			/* 先清掉当前树 */
			if (pool_ && root_ != npos()) clear();

			/* 若当前没有池，按源拥有模式补齐池 */
			if (!pool_) {
				if (other.pool_) {
					if (other.ownPool_) {
						size_t be = calc_block_exp(other.pool_->blockSize());
						pool_ = new arena<node_type>(be);
						ownPool_ = true;
					}
					else {
						pool_ = other.pool_;
						ownPool_ = false;
					}
				}
				else {
					/* 源也无池：保持空 */
					root_ = npos();
					return *this;
				}
			}

			root_ = npos();
			if (other.pool_ && other.root_ != npos())
				root_ = clone_subtree(other.root_, *other.pool_, *pool_);
			return *this;
		}

		/* 显式移动（C++03 风格）：窃取池指针与根索引，源置空 */
		void move(bitree& src)
		{
			if (&src == this) return;

			/* 清空自身并释放自有池（如有） */
			if (pool_ && root_ != npos()) clear();
			if (ownPool_ && pool_) { delete pool_; pool_ = NULL; }

			/* 窃取 */
			pool_ = src.pool_;
			ownPool_ = src.ownPool_;
			root_ = src.root_;

			/* 置空源（有效但未绑定） */
			src.pool_ = NULL;
			src.ownPool_ = false;
			src.root_ = npos();
		}

		~bitree() {

			/* 共享池不释放；仅独占时释放自建池指针 */
			if (ownPool_) { delete pool_; pool_ = NULL; }
			else  clear(); /* 本树所有节点返还给 arena（共享均需要） */
			root_ = npos();
		}

		bool ownsPool() const { return ownPool_; }

		/* 重新绑定外部 arena（会放弃原拥有权且清空根） */
		void rebind(arena<node_type>& sharedPool) {
			/* 先将当前树的节点返还到旧池，避免泄漏 */
			if (pool_ && root_ != npos()) clear();
			if (ownPool_ && pool_) { delete pool_; }
			pool_ = &sharedPool;
			ownPool_ = false;
			root_ = npos();
		}

		/* 仅独占模式下可真正清空/重置池（会影响共享者，谨慎） */
		void clearPoolOwned() { if (ownPool_ && pool_) pool_->clear(); }
		void resetPoolOwned() { if (ownPool_ && pool_) pool_->reset(); }

		/* 根/状态 */
		size_t root() const { return root_; }
		bool  empty() const { return root_ == npos(); }

		/* 访问节点 */
		node_type& at(size_t idx) { return (*pool_)[idx]; }
		const node_type& at(size_t idx) const { return (*pool_)[idx]; }
		node_type& operator[](size_t idx) { return (*pool_)[idx]; }
		const node_type& operator[](size_t idx) const { return (*pool_)[idx]; }

		/* 兼容旧命名（构造中调用 make_root） */
		inline size_t make_root(const T& v) { return makeRoot(v); }

		/* 构建/设置根：若不存在则创建；若已存在则仅更新值 */
		size_t makeRoot(const T& v) {
			if (root_ == npos()) {
				node_type n(v);
				root_ = pool_->create(n);
			}
			else {
				(*pool_)[root_].data = v;
			}
			return root_;
		}

		/* 创建一个孤立节点（未挂接到树）并返回其索引 */
		size_t createNode() { return pool_->create(); }
		size_t createNode(const T& v) {
			node_type n(v);
			return pool_->create(n);
		}

		/* 在 parent 左/右侧挂接新节点（若已有子树则先删） */
		size_t attachLeft(size_t parent, const T& v) {
			node_type& p = (*pool_)[parent];
			if (p.left != npos()) eraseSubtree(p.left);
			size_t child = createNode(v);
			p.left = child;
			return child;
		}
		size_t attachRight(size_t parent, const T& v) {
			node_type& p = (*pool_)[parent];
			if (p.right != npos()) eraseSubtree(p.right);
			size_t child = createNode(v);
			p.right = child;
			return child;
		}

		/* 仅设置已有子节点索引（不检测环） */
		void setLeft(size_t parent, size_t child) { (*pool_)[parent].left = child; }
		void setRight(size_t parent, size_t child) { (*pool_)[parent].right = child; }
		void setLeft(size_t child) { (*pool_)[root_].left = child; }
		void setRight(size_t child) { (*pool_)[root_].right = child; }


		/* 删除 parent 的左/右子树（若存在） */
		void detachLeft(size_t parent) {
			node_type& p = (*pool_)[parent];
			if (p.left != npos()) { eraseSubtree(p.left); p.left = npos(); }
		}
		void detachRight(size_t parent) {
			node_type& p = (*pool_)[parent];
			if (p.right != npos()) { eraseSubtree(p.right); p.right = npos(); }
		}

		/* 删除以 idx 为根的整棵子树（后序，回收到 freelist） */
		void eraseSubtree(size_t idx) {
			if (idx == npos()) return;
			vector<size_t> st;
			vector<char> vis;
			st.append(idx);  vis.append((char)0);
			while (st.count()) {
				size_t cur; char v;
				st.pop(cur); vis.pop(v);
				if (!v) {
					st.append(cur);  vis.append((char)1);
					node_type& nd = (*pool_)[cur];
					if (nd.right != npos()) { st.append(nd.right); vis.append((char)0); }
					if (nd.left != npos()) { st.append(nd.left); vis.append((char)0); }
				}
				else {
					node_type& nd = (*pool_)[cur];
					nd.left = nd.right = npos();
					pool_->erase(cur);
				}
			}
		}

		/* 清空本树（仅删本树节点，不影响共享池其他树） */
		void clear() {
			if (root_ != npos()) eraseSubtree(root_);
			root_ = npos();
		}
		void ForceClear()
		{
			root_ = npos();
		}
		/* 先/中/后序遍历（输出节点索引） */
		void PreOrder(vector<size_t>& out) const {
			out.clear();
			if (root_ == npos()) return;
			vector<size_t> st;
			st.append(root_);
			size_t cur;
			while (st.pop(cur)) {
				// 访问顺序：弹出即访问
				out.append(cur);
				const node_type& nd = (*pool_)[cur];
				// 先压右再压左 => 下次先处理左子树
				if (nd.right != npos()) st.append(nd.right);
				if (nd.left != npos()) st.append(nd.left);
			}
		}

		void InOrder(vector<size_t>& out) const {
			out.clear();
			vector<size_t> st;
			size_t cur = root_;
			// 经典迭代中序：一路向左入栈 -> 回溯访问 -> 转向右子树
			while (cur != npos() || st.count() != 0) {
				while (cur != npos()) {
					st.append(cur);
					cur = (*pool_)[cur].left;
				}
				st.pop(cur);               // 最左或回溯点
				out.append(cur);           // 访问根
				cur = (*pool_)[cur].right; // 处理右子树
			}
		}

		void PostOrder(vector<size_t>& out) const {
			out.clear();
			if (root_ == npos()) return;
			vector<size_t> st;
			vector<size_t> rev;            // 暂存反向序列
			st.append(root_);
			size_t cur;
			// 思路：收集“根-右-左”或“根-左-右”序列，逆序得到“左-右-根”
			while (st.pop(cur)) {
				rev.append(cur);           // 先记录当前节点
				const node_type& nd = (*pool_)[cur];
				// 这里选择：先压左后压右 => rev 中次序为 根, 右..., 左...
				if (nd.left != npos()) st.append(nd.left);
				if (nd.right != npos()) st.append(nd.right);
			}
			// 逆序输出 => 左子树..., 右子树..., 根
			for (size_t i = rev.count(); i != 0; --i)
				out.append(rev[i - 1]);
		}

		/* 调试：底层 arena 打印（共享池会打印同池所有节点） */
		void demo(FILE* fp) { pool_->demo(fp); }

		/* 访问底层 arena（必要时） */
		arena<node_type>& pool() { return *pool_; }
		const arena<node_type>& pool() const { return *pool_; }
		arena<node_type>* popPool() { ownPool_ = false; return pool_; }
	private:
		arena<node_type>* pool_;
		bool ownPool_;
		size_t root_;

		/* 从源池克隆一棵子树到目标池，返回新根索引 */
		static size_t clone_subtree(size_t srcRoot,
			arena<node_type>& srcPool,
			arena<node_type>& dstPool)
		{
			if (srcRoot == npos()) return npos();

			/* 建立 oldIdx -> newIdx 映射表（按源池 raw 上界） */
			vector<size_t> map;
			size_t upper = srcPool.rawUpperBound();
			map.recount(upper);
			for (size_t i = 0; i < upper; ++i) map[i] = npos();

			vector<size_t> st;
			vector<char> vis;
			st.append(srcRoot); vis.append((char)0);

			while (st.count()) {
				size_t cur; char v;
				st.pop(cur); vis.pop(v);
				const node_type& old = srcPool[cur];
				if (!v) {
					st.append(cur); vis.append((char)1);
					if (old.right != npos()) { st.append(old.right); vis.append((char)0); }
					if (old.left != npos()) { st.append(old.left);  vis.append((char)0); }
				}
				else {
					/* children 已克隆，克隆当前节点并修正左右索引 */
					node_type nn(old.data);
					size_t newIdx = dstPool.create(nn);
					node_type& ref = dstPool[newIdx];
					ref.left = (old.left == npos()) ? npos() : map[old.left];
					ref.right = (old.right == npos()) ? npos() : map[old.right];
					map[cur] = newIdx;
				}
			}
			return map[srcRoot];
		}

		/* 由 blockSize 推回 blockExp（blockSize=2^exp，exp<=20） */
		static size_t calc_block_exp(size_t blockSize)
		{
			size_t e = 0, x = 1;
			while (x < blockSize && e <= 20) { x <<= 1; ++e; }
			return e;
		}
	public:
		/* ===== 三阶段（前/中/后）统一迭代器 =====
   约定：
	 state = 0  前序点 (node 首次出现，左子尚未展开)
	 state = 1  中序点 (左子处理完，右子尚未展开)
	 state = 2  后序点 (左右处理完，节点结束)
   使用：while(it.still()){ if(it.state()==0)前序逻辑; else if(...) ...; it.next(); }
   可随时只关心某一类 state，即得到对应遍历。
*/
		class iter {
		public:
			typedef void _hx_need_explicit_move_tag;
			iter() : tree_(NULL) {}

			void initial(const bitree& t, size_t rootIdx = bitree::npos()) {
				tree_ = &t;
				stack.clear();
				size_t r = (rootIdx == bitree::npos() ? t.root_ : rootIdx);
				if (!tree_ || r == bitree::npos()) return;
				iteratorState fr; fr.site = r; fr.state = 0;
				stack.append(fr);
			}

			bool still() const { return stack.count() != 0; }

			int& state() { return stack.top().state; }
			const int& state() const { return stack.top().state; }
			size_t& target() { return stack.top().site; }
			const size_t& target() const { return stack.top().site; }

			/* 跳过左子树：在 state==0 调用，相当于直接进入中序 */
			void skipLeft() {
				if (!stack.count()) return;
				if (stack.top().state == 0) stack.top().state = 1;
			}
			/* 跳过右子树：在 state==1 调用，直接进入后序 */
			void skipRight() {
				if (!stack.count()) return;
				if (stack.top().state == 1) stack.top().state = 2;
			}
			/* 跳过整个剩余子树：在 state==0 或 1 调用，直接变后序（不会再下降） */
			void skipSubtree() {
				if (!stack.count()) return;
				if (stack.top().state != 2) stack.top().state = 2;
			}

			void next() {
				if (!tree_ || !stack.count()) return;
				iteratorState cur;
				if (!stack.pop(cur)) return;

				if (cur.state == 0) {
					// 前序 -> 压回中序点，再下潜左子
					iteratorState mid = cur; mid.state = 1;
					stack.append(mid);
					const node_type& nd = tree_->at(cur.site);
					if (nd.left != bitree::npos()) {
						iteratorState L; L.site = nd.left; L.state = 0;
						stack.append(L);
					}
				}
				else if (cur.state == 1) {
					// 中序 -> 压回后序点，再下潜右子
					iteratorState post = cur; post.state = 2;
					stack.append(post);
					const node_type& nd = tree_->at(cur.site);
					if (nd.right != bitree::npos()) {
						iteratorState R; R.site = nd.right; R.state = 0;
						stack.append(R);
					}
				}
				else {
					// 后序：完成，直接丢弃
				}
			}
			void move(iter& src) {
				if (&src == this) return;
				stack.move(src.stack);
				tree_ = src.tree_;
				src.tree_ = NULL;
			}
		private:
			const bitree* tree_;
			vector<iteratorState> stack;
		};

	};
}

/* ===================== 通用多叉树 (children vector 版) ===================== */
namespace hyperlex
{
	/* ---- gtreevNode：parent + children(vector<size_t>) + data ---- */
	template<class T>
	struct gtreevNode
	{
		size_t parent;
		vector<size_t> children;
		T      data;

		gtreevNode() : parent((size_t)-1), children(), data() {}
		explicit gtreevNode(const T& v) : parent((size_t)-1), children(), data(v) {}

		gtreevNode(const gtreevNode& rhs)
			: parent(rhs.parent), children(rhs.children), data(rhs.data) {
		}
		gtreevNode& operator=(const gtreevNode& rhs) {
			if (this != &rhs) {
				parent = rhs.parent;
				children = rhs.children;
				data = rhs.data;
			}
			return *this;
		}
		void move(gtreevNode& src) {
			if (this == &src) return;
			parent = src.parent;
			children.move(src.children);
			move_assign<T, need_explicit_move<T>::value>::apply(data, src.data);
		}
		void demo(FILE* fp) {
			fprintf(fp, "parent=%zu, childCount=%zu, data=", parent, children.count());
			data.demo(fp);
		}
	};

	template<class T>
	class gtreev
	{
	public:
		typedef gtreevNode<T> node_type;
		static inline size_t npos() { return (size_t)-1; }

		explicit gtreev(size_t blockExp = 8)
			: pool_(new arena<node_type>(blockExp)), ownPool_(true), root_(npos()) {
		}
		gtreev(const T& rootValue, size_t blockExp = 8)
			: pool_(new arena<node_type>(blockExp)), ownPool_(true), root_(npos()) {
			make_root(rootValue);
		}

		explicit gtreev(arena<node_type>& sharedPool)
			: pool_(&sharedPool), ownPool_(false), root_(npos()) {
		}
		gtreev(const T& rootValue, arena<node_type>& sharedPool)
			: pool_(&sharedPool), ownPool_(false), root_(npos()) {
			make_root(rootValue);
		}

		/* 深拷贝：保持源的拥有/共享模式 */
		gtreev(const gtreev& other)
			: pool_(NULL), ownPool_(false), root_(npos())
		{
			if (!other.pool_) return;
			if (other.ownPool_) {
				size_t be = calc_block_exp(other.pool_->blockSize());
				pool_ = new arena<node_type>(be);
				ownPool_ = true;
			}
			else {
				pool_ = other.pool_;
				ownPool_ = false;
			}
			if (other.root_ != npos())
				root_ = clone_subtree(other.root_, *other.pool_, *pool_);
		}

		gtreev& operator=(const gtreev& other)
		{
			if (this == &other) return *this;
			if (pool_ && root_ != npos()) clear();
			if (!pool_) {
				if (other.pool_) {
					if (other.ownPool_) {
						size_t be = calc_block_exp(other.pool_->blockSize());
						pool_ = new arena<node_type>(be);
						ownPool_ = true;
					}
					else {
						pool_ = other.pool_;
						ownPool_ = false;
					}
				}
				else { root_ = npos(); return *this; }
			}
			root_ = npos();
			if (other.pool_ && other.root_ != npos())
				root_ = clone_subtree(other.root_, *other.pool_, *pool_);
			return *this;
		}

		void move(gtreev& src)
		{
			if (&src == this) return;
			if (pool_ && root_ != npos()) clear();
			if (ownPool_ && pool_) { delete pool_; pool_ = NULL; }
			pool_ = src.pool_;
			ownPool_ = src.ownPool_;
			root_ = src.root_;
			src.pool_ = NULL;
			src.ownPool_ = false;
			src.root_ = npos();
		}

		~gtreev()
		{
			if (ownPool_) {
				delete pool_;
				pool_ = NULL;
			}
			else {
				clear();
			}
			root_ = npos();
		}

		bool ownsPool() const { return ownPool_; }
		size_t root() const { return root_; }
		bool empty() const { return root_ == npos(); }

		inline size_t make_root(const T& v) { return makeRoot(v); }

		size_t makeRoot(const T& v) {
			if (root_ == npos()) {
				node_type n(v);
				root_ = pool_->create(n);
			}
			else {
				(*pool_)[root_].data = v;
			}
			return root_;
		}

		size_t createNode() { return pool_->create(); }
		size_t createNode(const T& v) {
			node_type n(v);
			return pool_->create(n);
		}

		/* 追加子：尾部 O(1) 平摊（vector） */
		size_t appendChild(size_t parentIdx, const T& v)
		{
			size_t childIdx = createNode(v);
			node_type& p = (*pool_)[parentIdx];
			node_type& c = (*pool_)[childIdx];
			c.parent = parentIdx;
			p.children.append(childIdx);
			return childIdx;
		}

		/* 已存在节点挂接（要求该节点当前未挂接或由调用者确保安全） */
		void linkChild(size_t parentIdx, size_t childIdx)
		{
			node_type& p = (*pool_)[parentIdx];
			node_type& c = (*pool_)[childIdx];
			c.parent = parentIdx;
			p.children.append(childIdx);
		}

		/* 在指定位置插入（0..childCount）。若 pos>count 则附加到末尾 */
		size_t insertChild(size_t parentIdx, size_t pos, const T& v)
		{
			node_type& p = (*pool_)[parentIdx];
			size_t n = p.children.count();
			if (pos > n) pos = n;
			size_t childIdx = createNode(v);
			node_type& c = (*pool_)[childIdx];
			c.parent = parentIdx;

			/* 扩容 + 后移 */
			p.children.append((size_t)0); /* 增长一个占位 */
			for (size_t i = n; i > pos; --i)
				p.children[i] = p.children[i - 1];
			p.children[pos] = childIdx;
			return childIdx;
		}

		/* 移除父节点的第 i 个子（仅断开，不删除子树） */
		void detachChildAt(size_t parentIdx, size_t i)
		{
			node_type& p = (*pool_)[parentIdx];
			if (i >= p.children.count()) return;
			size_t childIdx = p.children[i];
			/* 左移收缩 */
			for (size_t j = i + 1; j < p.children.count(); ++j)
				p.children[j - 1] = p.children[j];
			p.children.recount(p.children.count() - 1);
			node_type& c = (*pool_)[childIdx];
			c.parent = npos();
		}

		/* 根据子索引值（节点 id）从父中移除（不删除子树） */
		void detachChild(size_t parentIdx, size_t childIdx)
		{
			node_type& p = (*pool_)[parentIdx];
			size_t n = p.children.count();
			for (size_t i = 0; i < n; ++i) {
				if (p.children[i] == childIdx) {
					detachChildAt(parentIdx, i);
					return;
				}
			}
		}

		/* 删除整棵子树（后序） */
		void eraseSubtree(size_t idx)
		{
			if (idx == npos()) return;
			vector<size_t> st;
			vector<char> vis;
			st.append(idx); vis.append((char)0);
			while (st.count()) {
				size_t cur; char v;
				st.pop(cur); vis.pop(v);
				node_type& nd = (*pool_)[cur];
				if (!v) {
					st.append(cur); vis.append((char)1);
					size_t cc = nd.children.count();
					for (size_t i = 0; i < cc; ++i) {
						st.append(nd.children[i]); vis.append((char)0);
					}
				}
				else {
					/* 先断开父引用中的自己（若还在） */
					if (nd.parent != npos() && pool_->alive(nd.parent)) {
						node_type& pr = (*pool_)[nd.parent];
						size_t cN = pr.children.count();
						for (size_t k = 0; k < cN; ++k) {
							if (pr.children[k] == cur) {
								for (size_t m = k + 1; m < cN; ++m)
									pr.children[m - 1] = pr.children[m];
								pr.children.recount(cN - 1);
								break;
							}
						}
					}
					/* 子向量清空（里面是 size_t 平凡类型） */
					nd.children.recount(0);
					nd.parent = npos();
					pool_->erase(cur);
				}
			}
		}

		void clear()
		{
			if (root_ != npos()) eraseSubtree(root_);
			root_ = npos();
		}
		/*强制清空 */
		void ForceClear()
		{
			root_ = npos();
		}
		/* 前序遍历（根-左到右） */
		void preOrder(vector<size_t>& out) const
		{
			out.clear();
			if (root_ == npos()) return;
			vector<size_t> st;
			st.append(root_);
			while (st.count()) {
				size_t cur; st.pop(cur);
				out.append(cur);
				const node_type& nd = (*pool_)[cur];
				size_t cc = nd.children.count();
				/* 逆序压栈保证从左到右访问 */
				for (size_t i = cc; i != 0; --i)
					st.append(nd.children[i - 1]);
			}
		}

		/* 后序遍历（子-根） */
		void postOrder(vector<size_t>& out) const
		{
			out.clear();
			if (root_ == npos()) return;
			vector<size_t> st;
			vector<char> vis;
			st.append(root_); vis.append((char)0);
			while (st.count()) {
				size_t cur; char v;
				st.pop(cur); vis.pop(v);
				const node_type& nd = (*pool_)[cur];
				if (!v) {
					st.append(cur); vis.append((char)1);
					size_t cc = nd.children.count();
					/* 从右到左压栈保证左子优先处理 */
					for (size_t i = cc; i != 0; --i) {
						st.append(nd.children[i - 1]); vis.append((char)0);
					}
				}
				else {
					out.append(cur);
				}
			}
		}

		/* 批量追加（用于“通配符产生式”展开），提前扩容降低多次 grow */
		template<class U>
		void appendChildrenBatch(size_t parentIdx, const U* elems, size_t count)
		{
			if (!count) return;
			node_type& p = (*pool_)[parentIdx];
			size_t old = p.children.count();
			p.children.ensure_capacity_for(count); /* 利用现有 ensure 逻辑（可调整：改成 public 或复制代码） */
			for (size_t i = 0; i < count; ++i) {
				size_t cidx = createNode(elems[i]);
				node_type& c = (*pool_)[cidx];
				c.parent = parentIdx;
				p.children.append(cidx);
			}
		}

		/* 访问与查询 */
		node_type& at(size_t idx) { return (*pool_)[idx]; }
		const node_type& at(size_t idx) const { return (*pool_)[idx]; }
		node_type& operator[](size_t idx) { return (*pool_)[idx]; }
		const node_type& operator[](size_t idx) const { return (*pool_)[idx]; }

		size_t childCount(size_t idx) const { return (*pool_)[idx].children.count(); }
		size_t child(size_t idx, size_t i) const {
			const node_type& nd = (*pool_)[idx];
			return i < nd.children.count() ? nd.children[i] : npos();
		}

		arena<node_type>& pool() { return *pool_; }
		const arena<node_type>& pool() const { return *pool_; }

		void rebind(arena<node_type>& sharedPool)
		{
			if (pool_ && root_ != npos()) clear();
			if (ownPool_ && pool_) delete pool_;
			pool_ = &sharedPool;
			ownPool_ = false;
			root_ = npos();
		}
		void clearPoolOwned() { if (ownPool_ && pool_) pool_->clear(); }
		void resetPoolOwned() { if (ownPool_ && pool_) pool_->reset(); }

		void demo(FILE* fp) { if (pool_) pool_->demo(fp); }

	private:
		arena<node_type>* pool_;
		bool ownPool_;
		size_t root_;

		static size_t clone_subtree(size_t srcRoot,
			arena<node_type>& srcPool,
			arena<node_type>& dstPool)
		{
			if (srcRoot == npos()) return npos();
			/* old -> new 索引映射 */
			vector<size_t> map;
			size_t upper = srcPool.rawUpperBound();
			map.recount(upper);
			for (size_t i = 0; i < upper; ++i) map[i] = npos();

			vector<size_t> st;
			vector<char> vis;
			st.append(srcRoot); vis.append((char)0);

			while (st.count()) {
				size_t cur; char v;
				st.pop(cur); vis.pop(v);
				const node_type& old = srcPool[cur];
				if (!v) {
					st.append(cur); vis.append((char)1);
					size_t cc = old.children.count();
					for (size_t i = 0; i < cc; ++i) {
						st.append(old.children[i]); vis.append((char)0);
					}
				}
				else {
					/* 子节点已克隆 */
					node_type nn(old.data);
					size_t newIdx = dstPool.create(nn);
					node_type& ref = dstPool[newIdx];
					ref.parent = npos();
					ref.children.recount(0);
					/* 重建子列表 */
					size_t cc = old.children.count();
					if (cc) {
						ref.children.recount(cc);
						for (size_t i = 0; i < cc; ++i) {
							size_t oldChild = old.children[i];
							size_t newChild = map[oldChild];
							ref.children[i] = newChild;
							dstPool[newChild].parent = newIdx;
						}
					}
					map[cur] = newIdx;
				}
			}
			return map[srcRoot];
		}

		static size_t calc_block_exp(size_t blockSize)
		{
			size_t e = 0, x = 1;
			while (x < blockSize && e <= 20) { x <<= 1; ++e; }
			return e;
		}
	public:
		/* ===== 简化版双阶段遍历迭代器（state=0 前序；state=1 后序）===== */
		class iter {
		public:
			iter() : tree_(NULL) {}

			/* rootIdx 省略则使用整棵树根；为空树则 still()==false */
			void initial(const gtreev& t, size_t rootIdx = gtreev::npos()) {
				tree_ = &t;
				stack.clear();
				if (!tree_ || (rootIdx == gtreev::npos() && t.root() == gtreev::npos()))
					return;
				size_t r = (rootIdx == gtreev::npos() ? t.root() : rootIdx);
				if (r != gtreev::npos()) {
					iteratorState s; s.site = r; s.state = 0;
					stack.append(s);
				}
			}

			bool still() const { return stack.count() != 0; }

			/* 当前栈顶状态引用： state=0 前序；state=1 后序 */
			int& state() { return stack.top().state; }
			size_t& target() { return stack.top().site; }
			const int& state() const { return stack.top().state; }
			const size_t& target() const { return stack.top().site; }

			/* 跳过当前节点的子树：直接把 state 设为 1 */
			void cutNow() {
				if (stack.count()) stack.top().state = 1;
			}

			/* 推进到下一步（一次弹栈展开或完成一个节点） */
			void next() {
				if (!tree_ || !stack.count()) return;
				iteratorState cur;
				if (!stack.pop(cur)) return;
				if (cur.state == 0) {
					/* 第一次遇到：压回后序标记，再压子节点（逆序保证左到右） */
					iteratorState after = cur;
					after.state = 1;
					stack.append(after);
					const node_type& nd = const_cast<gtreev*>(tree_)->at(cur.site);
					size_t cc = nd.children.count();
					for (size_t i = cc; i != 0; --i) {
						iteratorState ch; ch.site = nd.children[i - 1]; ch.state = 0;
						stack.append(ch);
					}
				}
				else {
					/* state == 1：后序阶段 -> 直接返回（下次由使用者读取栈顶或继续 next） */
					/* 什么也不做，调用者读取此时新的 stack.top()（若有）决定行为 */
				}
			}
			void move(iter& src) {
				if (&src == this) return;
				stack.move(src.stack);
				tree_ = src.tree_;
				src.tree_ = NULL;
			}
		private:
			const gtreev* tree_;
			vector<iteratorState> stack;
		};
	};

	
} 
/* ========================= 代表自动机的有向图 ============================== */
namespace hyperlex
{
	template<class Cv, class Ca>
	struct dgraph_arc {
		size_t from;
		size_t to;
		Ca     data;
		typedef void _hx_need_explicit_move_tag;
		dgraph_arc() : from(0), to(0), data() {}
		dgraph_arc(size_t f, size_t t, const Ca& d) : from(f), to(t), data(d) {}
		dgraph_arc(const dgraph_arc& rhs) : from(rhs.from), to(rhs.to), data(rhs.data) {}
		dgraph_arc& operator=(const dgraph_arc& rhs) {
			if (this != &rhs) { from = rhs.from; to = rhs.to; data = rhs.data; }
			return *this;
		}
		void move(dgraph_arc& src) {
			if (this == &src) return;
			from = src.from; to = src.to;
			move_assign<Ca, need_explicit_move<Ca>::value>::apply(data, src.data);
		}
	};

	template <class Cv, class Ca> class dgraph
	{
	public:

		struct vertex
		{
			vector<size_t> outArcs;
			vector<size_t> inArcs;
			Cv             data;
			typedef void _hx_need_explicit_move_tag;
			vertex() : outArcs(), inArcs(), data() {}
			vertex(const Cv& d) : outArcs(), inArcs(), data(d) {}
			vertex(const vertex& rhs)
				: outArcs(rhs.outArcs), inArcs(rhs.inArcs), data(rhs.data) {
			}
			vertex& operator=(const vertex& rhs) {
				if (this != &rhs) {
					outArcs = rhs.outArcs;
					inArcs = rhs.inArcs;
					data = rhs.data;
				}
				return *this;
			}
			void move(vertex& src) {
				if (&src == this) return;
				outArcs.move(src.outArcs);
				inArcs.move(src.inArcs);
				move_assign<Cv, need_explicit_move<Cv>::value>::apply(data, src.data);
			}
		};

		/* 原 dgraph 其它成员保持不变 … */

		explicit dgraph()
			: arcPool(new arena<dgraph_arc<Cv, Ca> >())
			, vertPool(new arena<vertex>())
			, ownPools(true)
		{
		}
		dgraph(arena<vertex>& vpool, arena<dgraph_arc<Cv, Ca> >& apool)
			: arcPool(&apool), vertPool(&vpool), ownPools(false)
		{
		}

		// 拷贝构造：深拷贝（保持 ownPools 语义；若源使用外部池，本对象仍使用“拥有”新池，避免共享池交叉写）
		dgraph(const dgraph& other)
			: arcPool(NULL), vertPool(NULL), ownPools(true)
		{
			// 策略：无论源是否 ownPools，这里都创建“自有”池，保证拷贝后独立
			arcPool = new arena<dgraph_arc<Cv, Ca> >();
			vertPool = new arena<vertex>();
			vertice.recount(0);

			// 1) 复制顶点（不连边）
			size_t vc = other.vertexCount();
			for (size_t i = 0; i < vc; ++i) {
				vertex nv;
				nv.data = other.atPos(i).data;
				// outArcs / inArcs 留空，稍后重建
				(void)vertPool->create(nv);
				vertice.append(i); // 维持 pos==index
			}
			// 2) 复制边并重建出入边表
			//   遍历源所有顶点的 outArcs，逐条新建
			for (size_t i = 0; i < vc; ++i) {
				const vertex& ov = other.atPos(i);
				for (size_t k = 0; k < ov.outArcs.count(); ++k) {
					const dgraph_arc<Cv, Ca> & oa = other.getArc(ov.outArcs[k]);
					dgraph_arc<Cv, Ca>  na;
					na.from = oa.from;
					na.to = oa.to;
					na.data = oa.data;
					size_t newId = arcPool->create(na);
					// 链接到新顶点的出/入边列表
					atPos(na.from).outArcs.append(newId);
					atPos(na.to).inArcs.append(newId);
				}
			}
		}

		// 拷贝赋值：先释放自身，再深拷贝（结果总是 ownPools=true，保持独立）
		dgraph& operator=(const dgraph& other)
		{
			if (this == &other) return *this;

			// 释放旧资源
			clear();
			if (ownPools && arcPool) { delete arcPool;  arcPool = NULL; }
			if (ownPools && vertPool) { delete vertPool; vertPool = NULL; }

			ownPools = true;
			arcPool = new arena<dgraph_arc<Cv, Ca> >();
			vertPool = new arena<vertex>();
			vertice.recount(0);

			size_t vc = other.vertexCount();
			for (size_t i = 0; i < vc; ++i) {
				vertex nv;
				nv.data = other.atPos(i).data;
				(void)vertPool->create(nv);
				vertice.append(i);
			}
			for (size_t i = 0; i < vc; ++i) {
				const vertex& ov = other.atPos(i);
				for (size_t k = 0; k < ov.outArcs.count(); ++k) {
					const dgraph_arc<Cv, Ca> & oa = other.getArc(ov.outArcs[k]);
					dgraph_arc<Cv, Ca>  na;
					na.from = oa.from;
					na.to = oa.to;
					na.data = oa.data;
					size_t newId = arcPool->create(na);
					atPos(na.from).outArcs.append(newId);
					atPos(na.to).inArcs.append(newId);
				}
			}
			return *this;
		}


		void move(dgraph& src)
		{
			if (&src == this) return;
			clear();
			if (ownPools && arcPool) { delete arcPool; arcPool = NULL; }
			if (ownPools && vertPool) { delete vertPool; vertPool = NULL; }

			arcPool = src.arcPool;
			vertPool = src.vertPool;
			ownPools = src.ownPools;
			vertice.move(src.vertice);

			src.arcPool = NULL;
			src.vertPool = NULL;
			src.ownPools = false;
			src.vertice.recount(0);
		}

		~dgraph()
		{
			if (ownPools) {
				delete arcPool;  arcPool = NULL;
				delete vertPool; vertPool = NULL;
			}
			else {
				clear();
			}
		}

		void rebind(arena<vertex>& vpool, arena<dgraph_arc<Cv, Ca> >& apool)
		{
			clear();
			if (ownPools) {
				delete arcPool;
				delete vertPool;
			}
			arcPool = &apool;
			vertPool = &vpool;
			ownPools = false;
			vertice.recount(0);
		}

		void resetPoolsOwned()
		{
			if (ownPools) {
				if (arcPool)  arcPool->reset();
				if (vertPool) vertPool->reset();
				vertice.recount(0);
			}
		}

		bool ownsPools() const { return ownPools; }

		// ===== 顶点/边 =====
		size_t addVertex()
		{
			vertex v;
			(void)vertPool->create(v); // arena id 不再外露/也不再需要反查
			size_t pos = vertice.count();
			vertice.append(pos);       // 仅占位，保持 pos == 下标 语义
			return pos;
		}
		size_t addVertex(const Cv& data)
		{
			vertex v; v.data = data;
			(void)vertPool->create(v);
			size_t pos = vertice.count();
			vertice.append(pos);
			return pos;
		}

		// 访问（按 pos）
		vertex& atPos(size_t pos) { return (*vertPool)[pos]; }
		const vertex& atPos(size_t pos) const { return (*vertPool)[pos]; }

		vertex& operator[](size_t pos) { return (*vertPool)[pos]; }
		const vertex& operator[](size_t pos) const { return (*vertPool)[pos]; }

		dgraph_arc<Cv, Ca> & getArc(size_t arcId) { return (*arcPool)[arcId]; }
		const dgraph_arc<Cv, Ca> & getArc(size_t arcId) const { return (*arcPool)[arcId]; }
		// 追加边（入参均为 pos）
		size_t addArcByPos(size_t fromPos, size_t toPos, const Ca& data)
		{
			dgraph_arc<Cv, Ca>  a; a.from = fromPos; a.to = toPos; a.data = data;
			size_t eid = arcPool->create(a);
			atPos(fromPos).outArcs.append(eid);
			atPos(toPos).inArcs.append(eid);
			return eid;
		}


		// 删除一条边（参数为 dgraph_arc<Cv, Ca>  的全局 id）
		void eraseArc(size_t arcId)
		{
			const dgraph_arc<Cv, Ca> & e = (*arcPool)[arcId];
			vertex& f = atPos(e.from);
			vertex& t = atPos(e.to);
			removeIdOnce(f.outArcs, arcId);
			removeIdOnce(t.inArcs, arcId);
			arcPool->erase(arcId);
		}

		// 清空整图
		void clear()
		{
			// 逐顶点删除关联的边
			for (size_t pos = 0; pos < vertice.count(); ++pos) {
				vertex& v = atPos(pos);
				while (v.outArcs.count()) {
					size_t eid = v.outArcs[v.outArcs.count() - 1];
					eraseArc(eid);
				}
				while (v.inArcs.count()) {
					size_t eid = v.inArcs[v.inArcs.count() - 1];
					eraseArc(eid);
				}
			}
			// 回收顶点
			for (size_t pos = 0; pos < vertice.count(); ++pos) {
				vertPool->erase(pos);
			}
			vertice.recount(0);
		}

		// 统计
		size_t vertexCount() const { return vertice.count(); }
		size_t outDegreeByPos(size_t pos) const { return atPos(pos).outArcs.count(); }
		size_t inDegreeByPos(size_t pos) const { return atPos(pos).inArcs.count(); }

		// ===== NFA：epsilon-闭包 =====
		// 要求： 使用本系列成员函数必须要求dgraph_arc<Cv, Ca> ::data含有 bool 成员 epsilon
		//要求： state.size() >= vertexCount()
		template<class T> void Closure(size_t startPos, T& state, vector<size_t>& stack) const
		{
			size_t n = vertexCount();
			state.value(false);
			if (startPos < n) state[startPos] = true;
			stack.clear();
			stack.append(startPos);
			size_t nowPos;
			while (stack.pop(nowPos) != 0) {
				const vertex& v = atPos(nowPos);
				const size_t m = v.outArcs.count();
				for (size_t k = 0; k < m; ++k) {
					const dgraph_arc<Cv, Ca> & e = (*arcPool)[v.outArcs[k]];
					if (e.data.epsilon) {
						size_t toPos = e.to; // 直接就是 pos
						if (toPos < n && !state[toPos]) {
							state[toPos] = true;
							stack.append(toPos);
						}
					}
				}
			}
		}
		template<class T> void Closure(T& state, vector<size_t>& stack) const
		{
			stack.clear();
			size_t n = vertexCount();
			for (size_t i = 0; i < n; ++i)
				if (state[i]) stack.append(i);

			size_t nowPos;
			while (stack.pop(nowPos) != 0) {
				const vertex& v = atPos(nowPos);
				const size_t m = v.outArcs.count();
				for (size_t k = 0; k < m; ++k) {
					const dgraph_arc<Cv, Ca> & e = (*arcPool)[v.outArcs[k]];
					if (e.data.epsilon) {
						size_t toPos = e.to; // 直接就是 pos
						if (toPos < n && !state[toPos]) {
							state[toPos] = true;
							stack.append(toPos);
						}
					}
				}
			}
		}
		inline void closure(size_t startPos, array<bool>& state, vector<size_t>& stack) const
		{
			Closure<array<bool>>(startPos, state, stack);
		}
		inline void closure(size_t startPos, vector<bool>& state, vector<size_t>& stack) const
		{
			Closure<vector<bool>>(startPos, state, stack);
		}
		inline void closure(array<bool>& state, vector<size_t>& stack) const
		{
			Closure<array<bool>>(state, stack);
		}
		void closure(vector<bool>& state, vector<size_t>& stack) const
		{
			Closure<vector<bool>>(state, stack);
		}
		inline static void stateToList(const array<bool>& state, vector<size_t>& out)
		{
			out.clear();
			size_t n = state.count();
			for (size_t i = 0; i < n; ++i) {
				if (state[i]) out.append(i);
			}
		}
	private:
		class arena<dgraph_arc<Cv, Ca> >* arcPool;
		class arena<vertex>* vertPool;
		bool ownPools;

		// pos 空间：保持 pos == 顶点在 vertPool 的顺序索引
		vector<size_t> vertice; // 仅作计数与兼容，值等于下标

		static inline void removeIdOnce(vector<size_t>& v, size_t id)
		{
			size_t n = v.count();
			for (size_t i = 0; i < n; ++i) {
				if (v[i] == id) {
					for (size_t j = i + 1; j < n; ++j) v[j - 1] = v[j];
					v.recount(n - 1);
					return;
				}
			}
		}

	};

	/* === dgraph::arc / dgraph::vertex traits 专用化 === */
	template<class Cv, class Ca>
	struct is_bitwise_relocatable< dgraph_arc<Cv, Ca> > {
		enum { value = is_bitwise_relocatable<Ca>::value };
	};
	template<class Cv, class Ca>
	struct is_trivially_destructible_like< dgraph_arc<Cv, Ca> > {
		enum { value = is_trivially_destructible_like<Ca>::value };
	};
	template<class Cv, class Ca>
	struct need_explicit_move< dgraph_arc<Cv, Ca> > {
		enum { value = need_explicit_move<Ca>::value };
	};


	/* vertex 内含 vector 与可能需要显式 move 的 Cv，统一保守处理 */
	//template<class Cv, class Ca>
	//struct is_bitwise_relocatable< typename dgraph<Cv, Ca>::vertex > { enum { value = 0 }; };
	//template<class Cv, class Ca>
	//struct is_trivially_destructible_like< typename dgraph<Cv, Ca>::vertex > { enum { value = 0 }; };
	//template<class Cv, class Ca>
	//struct need_explicit_move< typename dgraph<Cv, Ca>::vertex > { enum { value = 1 }; };

	// ==== dgraph 本体 traits（放在已有 arc/vertex traits 之后，且仅添加一次）====
	template<class Cv, class Ca>
	struct is_bitwise_relocatable< dgraph<Cv, Ca> > { enum { value = 0 }; };

	template<class Cv, class Ca>
	struct is_trivially_destructible_like< dgraph<Cv, Ca> > { enum { value = 0 }; };

	template<class Cv, class Ca>
	struct need_explicit_move< dgraph<Cv, Ca> > { enum { value = 1 }; };
}

namespace hyperlex
{
	// StringPool 类实现
	// 这是一个字符串池，用于存储唯一的字符串并提供快速访问
	// 它使用哈希表和向量来管理字符串，确保每个字符串都有一个唯一的ID。
	class charBuffer : public buffer<char>
	{
	public:
		//void operator<<(FILE* fp);
		const char* ptr(void) const;
		char* ptr(void);
		char* CopyVector(void) const;
		size_t CopyVector(vector<char>& storage, size_t& length) const;
		void copy(const charBuffer& source);

		void Append(const char* c);

		void operator=(const char* input);
		void operator=(const charBuffer& in);

		void operator+=(const char* source);
		void operator+=(long int source);
		void operator+=(double source);
		void operator+=(const charBuffer& in);

		void operator<<(char c);
		void operator<<(const char* c);
		void operator<<(double e);
		void operator<<(int e);
		void operator<<(long long int e);
		void operator<<(charBuffer& in);
		void operator<<(FILE* fp);

		bool operator==(size_t length);
		bool operator!=(size_t length);
		bool operator==(const charBuffer& in);
		bool operator!=(const charBuffer& in);
		bool operator!=(const char* srcR) const;


		long int DequeueInt(void);
		double DequeueReal(void);
		char DequeueChar(void);
		char* DequeueString(void);
		char* DequeueId(void);
	private:
		char QueueHead(void);
	};
	class stringConst : public array<char>
	{
	public:
		//约定，空串表示非唯一
		//当ptr == NULL时，表示空字符串""
		//当ptr != NULL, ptr[0] == '\0'(Length == 1)时，也表示空字符串
		//末尾跟着多个'\0'是非法的。末尾必须跟着一个'\0'
		/* 显式默认构造：为空串状态（Length=0, content=NULL） */
		stringConst() : array<char>() {}
		stringConst(const char* str);
		stringConst& operator=(const char* str);
		bool operator==(const stringConst& other) const;
		bool operator!=(const stringConst& other) const;
		bool operator!=(const char* other) const;
		bool operator==(const char* other) const;
		inline size_t length() const
		{
			return Length > 0 ? Length - 1 : 0;
		}
		inline const char* ptr() const
		{
			return Length > 0 ? content : "";
		}

	};
	template<> struct is_bitwise_relocatable<stringConst> { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like<stringConst> { enum { value = 0 }; };
	template<> struct need_explicit_move<stringConst> { enum { value = 1 }; };

	/*
========================================================
FilePath2
目的 / Purpose
--------------------------------------------------------
为编译器前端内部提供一个轻量、可组合、相对安全的路径片段容器：
- 以“分段 (segment)”形式存储路径，避免频繁的整体字符串拼接
- 支持构建、追加、裁剪、轻度规范化(normalize)与打印
- 适配你现有的 vector<stringConst> / charBuffer 内存模型
- 避免旧 FilePath 中大量手工 malloc/free 与易错的 ".." 特例分支

核心功能 / Features
--------------------------------------------------------
build(const char*):
	解析原始路径（接受混合 '/' '\'），提取段，记录是否绝对路径。
operator+=:
	右侧若为绝对路径则替换；否则逐段追加。
RearCut():
	删除最后一个段（或将绝对根退化为相对空）。
RearOnlyAppend():
	仅追加右侧最后一段。
RearCutAppend():
	先裁剪自身最后一段再整体（或尾段）拼接右侧。
normalize():
	- 去除 "." 段
	- 解析 ".."（回退上一级）。若已到最前：
		* 绝对路径：丢弃继续上行的 ".."
		* 相对路径：保留无法折叠的 ".."
	- 不做符号链接、真实文件系统查询
print(divide):
	返回一个新 charBuffer（临时路径串，不写回缓存）
path():
	返回（并必要时重建）内部缓存 FullPath 的 C 字符串
demo():
	调试展示

与旧 FilePath 的差异 / Differences vs FilePath
--------------------------------------------------------
1. 段存储：
   - 旧: vector<char*> + 手工 malloc/free
   - 新: vector<stringConst>，构造简单，生命周期由容器托管
2. 缓存策略：
   - 旧: 每次结构变动立即 refresh() 重建 char* FullPath
   - 新: rebuild_() 仍是立即策略；但 print() 不强制刷新缓存，可降低频度
3. 规范化策略：
   - 旧 clean() 里用“把被消解的对变成 '.' 再二次过滤”式技巧
   - 新 normalize() 直接构建 out 列表，更直观，可维护性更高
4. 异常 / 失败处理：
   - 仍不抛异常；输入为空返回空结构；不检查非法字符
5. 可移动性：
   - 提供 move(FilePath2&)；traits 标记 need_explicit_move=1（避免容器做位拷贝）

复杂度 / Complexity
--------------------------------------------------------
- 构建 build: O(L)  L=输入路径长度
- 追加 / 裁剪: O(段数变动)（不复制历史段内容，只复制 stringConst 包装）
- normalize: O(N)  N=当前段数
- rebuild_: O(N + 总字符数)
适用于“配置 / include / DSL 小文件”场景，典型段数较小（<64）时开销可忽略。

设计取舍 / Trade-offs
--------------------------------------------------------
+ 保留最小职责：不做真实文件存在性、大小写 fold、符号链接解析、UNC/驱动器解析。
+ 不依赖 <filesystem>，保持纯 C++98/11 低要求环境兼容性（与你现有代码风格一致）。
+ 允许相对路径中保留前导无法折叠的 ".." —— 保守而透明。
- 不缓存分段哈希；大量重复比较 (==) 仍是线性段对比（当前使用场景足够）。
- 未提供大小写不敏感比较；在 Windows 语义下可能出现逻辑重复。
- 未做 Unicode NFC/NFD 归一；多平台文件名规范化留给更高层。
- normalize() 不会合并产生空路径用“.” 表示（保持语义最简化）。
- 线程安全性：实例级别无共享静态，但外部并发写需自行同步。

潜在扩展 / Possible Extensions
--------------------------------------------------------
1. 提供 toKey(bool lowerCase) 生成 include 判重 Key（统一分隔、可选大小写折叠）
2. 增加 resolveRelative(const FilePath2& base) 做基路径合成
3. 引入简易缓存：记录上次 rebuild_ 的段计数与哈希，避免重复重建
4. 添加 fromParent() / parent() / stem() / extension() 等查询便捷函数
5. 可选编译期开关支持大小写折叠或平台差异策略

局限 / Limitations
--------------------------------------------------------
- 不保证路径语义等价（./a/../b 与 b 规范化后相同，但符号链接场景仍可能不同）
- 不处理 Windows 盘符（如 "C:\\" 被当作 'C:' 段 + 绝对标记后续不保留冒号）
- 不处理网络路径 (\\server\share) 的专门语义
- 不检测段内非法字符（如嵌入 '\0' 不可达，但保留潜在控制符）
- 不是安全沙箱：不会阻止路径上溯超出工程根的构造
- 与真实文件系统状态（大小写敏感与否、链接）无同步机制

使用建议 / Usage Tips
--------------------------------------------------------
1. include 判重：
   - build() + normalize() 后用 print('/') 或 path() 生成 Key
   - 可再做一次将多个 '/' 折叠与大小写折叠（按平台）提高命中率
2. 若频繁只做“追加最后一段” -> 优先 RearOnlyAppend 避免多余段复制
3. 对性能敏感路径批处理：累积修改后再一次 normalize() 减少中间重建

示例 / Example
--------------------------------------------------------
FilePath2 a; a.build("/usr/local/../include/./m"); a.normalize(); // /usr/include/m
FilePath2 b; b.build("src/core/file.cpp");
FilePath2 rel; rel.build("../inc/header.h");
b.RearCutAppend(rel); // src/inc/header.h
b.normalize();
fprintf(stdout, "%s\n", b.path());

========================================================
*/
	// === FilePath2 修正后的声明（替换原有声明） ===
	class FilePath2
	{
	protected:
		bool absolute;
		vector<stringConst> PathUnit;
		charBuffer FullPath; // 缓存的完整路径（按 '/' 构建）

		void rebuild_();      // 重建 FullPath
	public:
		FilePath2();
		FilePath2(const FilePath2& rhs);
		~FilePath2();
		void move(FilePath2& src);
		FilePath2& operator=(const FilePath2& rhs);

		void build(const char* path);
		void operator+=(const FilePath2& rhs);
		bool operator==(const FilePath2& rhs) const;
		charBuffer print(char divide = '/') const; // 生成临时表示
		const char* path() const;                  // 返回缓存（必要时重建）
		void demo(FILE* fp = stdout) const;
		void copy(const FilePath2& source);

		void RearCut();
		void RearCutAppend(const FilePath2& rhs);
		void RearOnlyAppend(const FilePath2& rhs);
		void clear();
		void normalize(); // 逻辑等价旧 FilePath::clean()
	};

	// === FilePath2 traits（放在 FilePath2 定义之后同命名空间内）===
	template<> struct is_bitwise_relocatable<FilePath2> { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like<FilePath2> { enum { value = 0 }; };
	template<> struct need_explicit_move<FilePath2> { enum { value = 1 }; };

	class FilePath
	{
	public:
		FilePath();
		~FilePath();
		void build(const char* path);
		void operator+=(const FilePath& path);
		//the input path can't be 'this'。 A += A is wrong;
		bool operator==(const FilePath& rhs) const;
		char* print(char divide = '/')const;
		const char* path(void) const;
		void demo(FILE* fp = stdout)const;
		void copy(const FilePath& source);
		//the input path can't be 'this'。 A += A is wrong;
		void RearCut(void);
		void RearCutAppend(const FilePath& rhs);
		void RearOnlyAppend(const FilePath& rhs);
		void clear(void);
		void clean(void);
	private:
		bool absolute;
		vector<char*> PathUnit;
		char* FullPath;
		void refresh(void);
		void append_copy(const char* str);
	};
	
	/* ================= MurmurHash (public domain, Austin Appleby) =================
	   简化版：
	   - 64 位平台：MurmurHash64A
	   - 32 位平台：MurmurHash2
	   参考实现已裁剪为只返回一个 size_t。
	*/
	inline static size_t _hx_murmur_rotl64(size_t x, int r) {
#if SIZE_MAX > 0xffffffffUL
		return (x << r) | (x >> (64 - r));
#else
		return (size_t)(((x << r) | (x >> (32 - r))) & 0xffffffffUL);
#endif
	}

	/* 核心字节哈希函数（对任意字节序列） */
	inline static size_t _hx_murmur_bytes(const void* key, size_t len, size_t seed)
	{
#if SIZE_MAX > 0xffffffffUL
		/* 64-bit: MurmurHash64A */
		const uint64_t m = 0xc6a4a7935bd1e995ULL;
		const int r = 47;
		uint64_t h = (uint64_t)seed ^ (len * m);

		const uint64_t* data = (const uint64_t*)key;
		const uint64_t* end = data + (len / 8);

		while (data != end) {
			uint64_t k = *data++;
			k *= m;
			k ^= k >> r;
			k *= m;

			h ^= k;
			h *= m;
		}

		const unsigned char* data2 = (const unsigned char*)data;
		switch (len & 7) {
		case 7: h ^= (uint64_t)data2[6] << 48;
		case 6: h ^= (uint64_t)data2[5] << 40;
		case 5: h ^= (uint64_t)data2[4] << 32;
		case 4: h ^= (uint64_t)data2[3] << 24;
		case 3: h ^= (uint64_t)data2[2] << 16;
		case 2: h ^= (uint64_t)data2[1] << 8;
		case 1: h ^= (uint64_t)data2[0]; h *= m;
		default: break;
		}

		h ^= h >> r;
		h *= m;
		h ^= h >> r;
		return (size_t)h;
#else
		/* 32-bit: MurmurHash2 */
		const uint32_t m = 0x5bd1e995UL;
		const int r = 24;
		uint32_t h = (uint32_t)seed ^ (uint32_t)len;

		const unsigned char* data = (const unsigned char*)key;

		while (len >= 4) {
			uint32_t k = *(uint32_t*)data;
			k *= m;
			k ^= k >> r;
			k *= m;

			h *= m;
			h ^= k;

			data += 4;
			len -= 4;
		}

		switch (len) {
		case 3: h ^= (uint32_t)data[2] << 16;
		case 2: h ^= (uint32_t)data[1] << 8;
		case 1: h ^= (uint32_t)data[0]; h *= m;
		default: break;
		}

		h ^= h >> 13;
		h *= m;
		h ^= h >> 15;
		return (size_t)h;
#endif
	}

	/* 对 stringConst 计算哈希（空串安全） */
	inline size_t hashKey(const stringConst& src)
	{
		const char* p = src.ptr();
		size_t len = src.length();
		/* 固定种子（可按需修改/参数化） */
#if SIZE_MAX > 0xffffffffUL
		const size_t seed = (size_t)0x9e3779b97f4a7c15ULL;
#else
		const size_t seed = (size_t)0x9e3779b9UL;
#endif
		return _hx_murmur_bytes(p, len, seed);
	}

	/* 对 vector<size_t> 计算哈希
	   注意：直接使用底层内存布局，不同平台（32/64 位、大小端）结果不同。
	   若需跨平台稳定，可改成逐元素按固定 64 位小端序序列化后再喂入 _hx_murmur_bytes。
	*/
	inline size_t hashKey(const vector<size_t>& src)
	{
		size_t n = src.count();
		const void* data = (const void*)src.ptr(); /* ptr() 返回底层数组首地址 */
		size_t bytes = n * sizeof(size_t);
#if SIZE_MAX > 0xffffffffUL
		const size_t seed = (size_t)0x6a09e667f3bcc909ULL;
#else
		const size_t seed = (size_t)0x6a09e667UL;
#endif
		return _hx_murmur_bytes(data, bytes, seed ^ (n * 0x51ed2705UL));
	}

	/*
	假定 T 支持：
		- 复制构造与析构
		- bool operator == const 成员函数
		- size_t hashKey(const T&) const 全局同名函数
	hash 返回的id从 1 开始，0 表示未找到。
	*/
	template<class T>
	class hash
	{
	protected:
		array<size_t> hashBuckets; /* 0=空；>0=id */
		size_t        logCap;// 桶数 = 2^logCap
		double        LOAD_FACTOR;
		size_t        filled;
		size_t        filledLimit;
		vector<T>     content;     /* id = index + 1 */
		// 新增：计算探测步长（>=1 的奇数，依赖 hash 值）
		inline size_t probeStep_(size_t h) const {
			size_t mask = ((size_t)1 << logCap) - 1;
			// 取 hash 的高/中位做一次再混合，得到 0..mask
			size_t step = ((h >> logCap) ^ (h >> (logCap > 1 ? (logCap / 2) : 1))) & mask;
			step |= (size_t)1;           // 保证为奇数
			if (step == 0) step = 1;     // 兜底
			return step;
		}
		inline bool appendCore(const T& key, size_t& Infor)
		{
			size_t h = hashKey(key);
			size_t mask = ((size_t)1 << logCap) - 1;
			size_t step = probeStep_(h);
			size_t pos = h & mask;
			/* 1) 原表探测：找现有或首个空槽 */
			for (;;) {
				size_t sid = hashBuckets[pos];
				if (sid == 0) break;                 // 记住 pos 供插入
				if (content[sid - 1] == key)
				{
					Infor = sid;
					return true; // 已存在
				}
				pos = (pos + step) & mask;
			}

			/* 2) 真要新增，先检查是否需要扩容；扩容后用同一个 h 重新找空槽 */
			if (filled + 1 > filledLimit) {
				grow_(); // 会重新分配桶并清空
				mask = ((size_t)1 << logCap) - 1;
				step = probeStep_(h);
				pos = h & mask;
				while (hashBuckets[pos]) {
					pos = (pos + step) & mask;
				}
			}
			Infor = pos;
			
			return false;
		}
	public:
		enum { npos_enum = 0 };
		static inline size_t npos() { return (size_t)0; }

		/* 传入的是 2 的幂的对数：桶数 = 2^logCapInit；默认 8 => 256 桶 */
		hash(size_t logCapInit = 8, double load = 0.25)
			: logCap(0)
			, LOAD_FACTOR(load <= 0.0 ? 0.25 : load)
			, filled(0)
			, filledLimit(0)
		{
			if (logCapInit < 3) logCapInit = 3;
			const size_t maxShift = (sizeof(size_t) * 8 - 2);
			if (logCapInit > maxShift) logCapInit = maxShift;
			logCap = logCapInit;
			initBuckets_();
		}

		/* ===== 拷贝构造：深拷贝桶与内容 ===== */
		hash(const hash& other)
			: hashBuckets()
			, logCap(other.logCap)
			, LOAD_FACTOR(other.LOAD_FACTOR)
			, filled(other.filled)
			, filledLimit(other.filledLimit)
			, content(other.content)
		{
			size_t bc = ((size_t)1) << logCap;
			hashBuckets.Malloc(bc);
			for (size_t i = 0; i < bc; ++i)
				hashBuckets[i] = other.hashBuckets[i];
		}

		/* 拷贝赋值：先自清桶，再深拷贝 */
		hash& operator=(const hash& other) {
			if (this == &other) return *this;
			/* 复制标量与内容向量 */
			logCap = other.logCap;
			LOAD_FACTOR = other.LOAD_FACTOR;
			filled = other.filled;
			filledLimit = other.filledLimit;
			content = other.content;
			/* 重建桶 */
			size_t bc = ((size_t)1) << logCap;
			hashBuckets.Malloc(bc);
			for (size_t i = 0; i < bc; ++i)
				hashBuckets[i] = other.hashBuckets[i];
			return *this;
		}

		/* 显式移动：窃取桶与内容；源置空（满足 need_explicit_move） */
		void move(hash& src) {
			if (&src == this) return;
			hashBuckets.move(src.hashBuckets);   /* array<T>::move 已实现指针窃取 */
			content.move(src.content);           /* vector<T>::move */
			logCap = src.logCap;
			LOAD_FACTOR = src.LOAD_FACTOR;
			filled = src.filled;
			filledLimit = src.filledLimit;

			/* 置空源（保持可析构、可再次使用） */
			src.logCap = 0;
			src.filled = 0;
			src.filledLimit = 0;
			/* 保留 src.LOAD_FACTOR 不强制改动，维持逻辑默认值 */
		}


		~hash() {
			hashBuckets.Free();
			content.clear();
			filled = 0;
			filledLimit = 0;
			logCap = 0;
		}

		
		inline size_t append(const T& key) 
		{
			size_t Infor = 0;
			if (!appendCore(key, Infor))
			{
				size_t idx = content.count();
				content.append(key);
				size_t Id = idx + 1;
				hashBuckets[Infor] = Id;
				++filled;
				return Id;
			}
			return Infor;
		}
		inline size_t appendMove(T &key) 
		{
			size_t Infor = 0;
			if (!appendCore(key, Infor))
			{
				size_t idx = content.count();
				content.appendMove(key);
				size_t Id = idx + 1;
				hashBuckets[Infor] = Id;
				++filled;
				return Id;
			}
			return Infor;
		}

		size_t find(const T& key) const {
			if (filled == 0) return 0;
			const size_t mask = ((size_t)1 << logCap) - 1;
			size_t h = hashKey(key);
			size_t pos = h & mask;
			size_t step = probeStep_(h);
			for (;;) {
				size_t sid = hashBuckets[pos];
				if (sid == 0) return 0;
				if (content[sid - 1] == key) return sid;
				pos = (pos + step) & mask;
			}
		}

		const T* get(size_t id) const {
			if (id == 0) return (const T*)0;
			size_t idx = id - 1;
			return idx < content.count() ? &content[idx] : (const T*)0;
		}
		const T& operator[](size_t id) const { return content[id - 1]; }

		inline size_t size() const { return content.count(); }
		inline bool   empty() const { return content.count() == 0; }
		inline size_t bucketCount() const { return (size_t)1 << logCap; }
		inline size_t bucketLog() const { return logCap; }
		inline double currentLoad() const {
			size_t bc = bucketCount();
			return bc ? (double)filled / (double)bc : 0.0;
		}

		void clear() {
			hashBuckets.value(0);
			content.clear();
			filled = 0;
			filledLimit = (size_t)(bucketCount() * LOAD_FACTOR);
			if (filledLimit == 0) filledLimit = 1;
		}
		inline size_t countCollisions() const {
			if (filled == 0) return 0;
			size_t mask = ((size_t)1 << logCap) - 1;
			size_t collisions = 0;
			size_t bc = bucketCount();
			for (size_t pos = 0; pos < bc; ++pos) {
				size_t id = hashBuckets[pos];
				if (id == 0) continue;
				/* 计算该元素的 home 桶 */
				size_t h = hashKey(content[id - 1]);
				size_t home = h & mask;
				if (home != pos) ++collisions; /* 被探测/漂移过 */
			}
			return collisions;
		}
		void demo(FILE* fp = stdout) const {
			fprintf(fp, "hash summary:\n");
			fprintf(fp, "  collisions  : %zu\n", countCollisions());
			fprintf(fp, "  logCap      : %zu\n", logCap);
			fprintf(fp, "  buckets     : %zu\n", bucketCount());
			fprintf(fp, "  elements    : %zu\n", content.count());
			fprintf(fp, "  filledSlots : %zu\n", filled);
			fprintf(fp, "  loadFactor  : %.3f (current=%.3f)\n",
				LOAD_FACTOR, currentLoad());
		}


	private:
		void initBuckets_() {
			size_t bc = (size_t)1 << logCap;
			hashBuckets.Malloc(bc);
			hashBuckets.value(0);
			filled = 0;
			filledLimit = (size_t)(bc * LOAD_FACTOR);
			if (filledLimit == 0) filledLimit = 1;
		}

		void grow_() {
			++logCap;
			/* 重新分配新桶并重置 filled / filledLimit */
			initBuckets_();
			/* 重新散列所有现存元素（id = index + 1） */
			size_t n = content.count();
			for (size_t i = 0; i < n; ++i) {
				insertId_(i + 1);
			}
		}

		void insertId_(size_t id) {
			const size_t mask = ((size_t)1 << logCap) - 1;
			size_t h = hashKey(content[id - 1]);
			size_t pos = h & mask;
			size_t step = probeStep_(h);
			while (hashBuckets[pos]) {
				pos = (pos + step) & mask;
			}
			hashBuckets[pos] = id;
			++filled;
		}



	};
	/* ===== hash<T> traits 专用化 ===== */
	template<class T> struct is_bitwise_relocatable< hash<T> > { enum { value = 0 }; };
	template<class T> struct is_trivially_destructible_like< hash<T> > { enum { value = 0 }; };
	template<class T> struct need_explicit_move< hash<T> > { enum { value = 1 }; };
	/* ================= StringPool =================
	   字符串池，存储唯一字符串并提供快速访问
	   - insert(const char* str) : 插入字符串，返回其唯一 ID（从 1 开始，0 表示空串）
	   - getString(size_t id)    : 按 ID 获取字符串指针（id=0 返回 ""）
	*/
	class StringPool : public hash<stringConst>
	{
	public:
		size_t insert(const char* str) {
			if (str == NULL) str = "";
			stringConst sc(str);
			return append(sc);
		}
		size_t insertMove(charBuffer& str) {
			if (str.count() == 0) {
				stringConst sc("");
				return append(sc);
			}
			stringConst sc(str.ptr());
			return appendMove(sc);
		}
		const char* getString(size_t id) const {
			const stringConst* p = get(id);
			return p ? p->ptr() : "";
		}
	};
	template<> struct is_bitwise_relocatable<StringPool> { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like<StringPool> { enum { value = 0 }; };
	template<> struct need_explicit_move<StringPool> { enum { value = 1 }; }; // 目前没写 move(StringPool&)


}
namespace hyperlex
{
	class TokenStream
	{
	public:
		TokenStream();
		TokenStream(StringPool* pool);
		~TokenStream();
		TokenStream(const TokenStream& src);
		TokenStream& operator=(const TokenStream& src);
		void move(TokenStream& src);
		void clear(void);
		struct token
		{
			int accept;
			size_t id;
			unsigned int block;
			bool valid() const { return accept > 0; }
		};
		struct segment
		{
			size_t file;             // 源文件编号
			size_t TokenCount;       // 段内 token 数（行哨兵不含在内，lines.back()==TokenCount）
			size_t physicalOffest;   // 段第一个 token 在全局 tokens 向量中的物理下标
			size_t virtualOffest;    // 段第一个 token 的“虚拟”序号（如宏展开后的逻辑偏移）
			size_t fileLineOffset;   // 段首行在其所属文件中的行号基
			size_t globalLineOffset; // 段首行在全局行号空间中的行号基
			vector<unsigned int> lines; // 行首 token 的段内偏移

			inline segment()
				: file(0)
				, TokenCount(0)
				, physicalOffest(0)
				, virtualOffest(0)
				, fileLineOffset(0)
				, globalLineOffset(0)
				, lines() {
			}

			inline segment(const segment& rhs)
				: file(rhs.file)
				, TokenCount(rhs.TokenCount)
				, physicalOffest(rhs.physicalOffest)
				, virtualOffest(rhs.virtualOffest)
				, fileLineOffset(rhs.fileLineOffset)
				, globalLineOffset(rhs.globalLineOffset)
				, lines(rhs.lines) {
			}

			inline segment& operator=(const segment& rhs) {
				if (this != &rhs) {
					file = rhs.file;
					TokenCount = rhs.TokenCount;
					physicalOffest = rhs.physicalOffest;
					virtualOffest = rhs.virtualOffest;
					fileLineOffset = rhs.fileLineOffset;
					globalLineOffset = rhs.globalLineOffset;
					lines = rhs.lines;
				}
				return *this;
			}

			inline void move(segment& src) {
				if (&src == this) return;
				file = src.file;
				TokenCount = src.TokenCount;
				physicalOffest = src.physicalOffest;
				virtualOffest = src.virtualOffest;
				fileLineOffset = src.fileLineOffset;
				globalLineOffset = src.globalLineOffset;
				lines.move(src.lines);
				// 置空源
				src.file = 0;
				src.TokenCount = 0;
				src.physicalOffest = 0;
				src.virtualOffest = 0;
				src.fileLineOffset = 0;
				src.globalLineOffset = 0;
			}

			inline ~segment() {}
		};
		
	protected:
		StringPool* Pool;
		bool ownPool;
		vector<token> tokens;
		vector<segment> segments;
		//一定按照虚拟地址的首地址升序排列，并且没有虚拟地址重名
		vector<stringConst> SrcFile;
		bool realMode;//实模式下，虚拟地址等于物理地址，不进行转换
	public:
		// 虚拟地址 -> 物理地址
		inline size_t VtoP(size_t vpos) const
		{
			if (realMode || segments.count() == 0) return vpos;
			// 二分定位所属 segment
			size_t lo = 0, hi = segments.count();
			while (lo < hi)
			{
				size_t mid = (lo + hi) >> 1;
				const segment& seg = segments[mid];
				// 若 vpos 在当前段左侧
				if (vpos < seg.virtualOffest)
				{
					hi = mid;
					continue;
				}
				// 计算段右开界限（避免溢出：先减再比）
				size_t rel = vpos - seg.virtualOffest;
				if (rel >= seg.TokenCount)
				{
					lo = mid + 1;
					continue;
				}
				// 命中
				return seg.physicalOffest + rel;
			}
			// 未找到：越界
			assert(false && "TokenStream::VtoP() virtual index out of range");
			return vpos; // 兜底
		}

		// 覆盖 operator[]：现在按“虚拟地址”访问
		inline const token& operator[](size_t vpos) const
		{
			size_t p = VtoP(vpos);
			return tokens[p];
		}
		inline token& operator[](size_t vpos)
		{
			size_t p = VtoP(vpos);
			return tokens[p];
		}
		inline StringPool* GetPool(void) const { return Pool; }
		inline size_t TokenCount(void) const {return tokens.count();}
		inline const token& atToken(size_t pos) const { return tokens[pos]; }

		inline const char* getString(size_t pos) const
		{
			const token& t = atToken(pos);
			size_t id = t.id;
			return Pool->getString(id);
		}
		inline const stringConst & getStringC(size_t pos) const
		{
			const token& t = atToken(pos);
			size_t id = t.id;
			return *(Pool->get(id));
		}
		inline const char* getFileName(size_t fileNo) const
		{
			if (fileNo >= SrcFile.count()) return "";
			return SrcFile[fileNo].ptr();
		}
		
	public:
		void Demo(FILE* fp) const;
		inline size_t FileCount(void) const;
		
		
		size_t searchLine(size_t No) const;
		size_t searchFile(size_t No) const;
		bool locate(size_t tokenNo, size_t& outFile, size_t& outLine, size_t& outColumn) const;
			/* 若只需行数相当于Block开始的位移： */
		bool lineRange(size_t tokenNo, size_t& lineOffest, size_t& outColumn) const;
	};

	// === TokenStream 相关 traits (放在 TokenStream 定义之后，仍在 namespace hyperlex 内) ===
	template<> struct is_bitwise_relocatable< TokenStream::token > { enum { value = 1 }; };
	template<> struct is_trivially_destructible_like< TokenStream::token > { enum { value = 1 }; };

	// === TokenStream 相关 traits (block 替换为 segment) ===
	template<> struct is_bitwise_relocatable< TokenStream::segment > { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like< TokenStream::segment > { enum { value = 0 }; };
	template<> struct need_explicit_move< TokenStream::segment > { enum { value = 1 }; };


	template<> struct is_bitwise_relocatable< TokenStream > { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like< TokenStream > { enum { value = 0 }; };
	template<> struct need_explicit_move< TokenStream > { enum { value = 1 }; };
}
namespace hyperlex
{
	class RegExp
	{
	public:
		enum NodeType
		{
			Concatenation = 0,
			Alternation = 1,
			ZeroOrMore = 2,
			OneOrMore = 3,
			ZeroOrOne = 4,
			Range = 5,
			RepeatInterval = 6,
		};
		struct item : public closedInterval
		{
			NodeType type;
			void Demo(FILE* fp);
			void copy(const item& source);
		};
	private:
		arena<bitreeNode<item>> pool_;
		bitree<item> tree_;
	public:
		RegExp();
		~RegExp();
		RegExp(const RegExp& src);
		RegExp& operator=(const RegExp& src);
		void move(RegExp& src);
		void clear(void);

		int build(const char* expression);
		void Demo(FILE* fp = stdout) const;
		void Demo(size_t tabs, FILE* fp) const;
		static void DemoNode(FILE* fp, NodeType T);
		static void DemoRange(FILE* fp, int L, int U);
	private:
		size_t CreateNode(NodeType type, int L, int U);
	};
}
namespace hyperlex
{
	class LR0;
	class LR1;
	class grammer
	{
	public:
		friend class LR0;
		friend class LR1;
		friend class LRTable;
		grammer();
		~grammer();
		grammer(const grammer& other);
		grammer& operator=(const grammer& other);
		void move(grammer& src);

		// 元数据
		inline size_t nonterminalCount() const { return symbols.count(); }
		inline size_t terminalCount()   const { return terminal.count(); }
		void clear(); // 清空整个文法到初始状态
		// 指定开始符（按非终结符下标）
		void setStartSymbol(size_t ntIndex);
		size_t startSymbol() const;

		

		// 只读访问某个非终结符的 FIRST/FOLLOW 行（列宽 = terminalCount()+2）
		const array<bool>& firstOf(size_t ntIndex) const;
		const array<bool>& followOf(size_t ntIndex) const;

		struct production
		{
			size_t symbol;// 该产生式的左部非终结符号，对应与symbol的下标
			sint priority;//优先级，数值越大优先级越高
			//用于解决移进归约冲突，不解决规约规约冲突
			//如果优先级相同则无法解决冲突
			//如果优先级不同则优先级高的动作被执行
			//默认优先级为0
			charBuffer name;//每个产生式的名字。
			bool assoc;//associativity: 0 no, 1 yes
			bool assocL;//associativity: 0 left, 1 right
			vector<sint> content;// 产生式的内容, 正数和零代表终结符号，负数代表非终结符号
			//负数的绝对值减一代表nonterminal的下标
			//正数和零代表ternimal的下标
			//0代表文件终止。它的符号固定是 '#'并且被认为是一个终结符号 
			inline sint& operator[](size_t i) { return content[i]; }
			inline const sint& operator[](size_t i) const { return content[i]; }
			inline size_t size(void) const { return content.count(); }

			production()
				: symbol(0), priority(0), name(), assoc(false), assocL(true), content() {
			}
			production(const production& rhs)
				: symbol(rhs.symbol), priority(rhs.priority), name(rhs.name),
				assoc(rhs.assoc), assocL(rhs.assocL), content(rhs.content) {
			}
			production& operator=(const production& rhs) {
				if (this != &rhs) {
					symbol = rhs.symbol;
					priority = rhs.priority;
					name = rhs.name;
					assoc = rhs.assoc;
					assocL = rhs.assocL;
					content = rhs.content;
				}
				return *this;
			}
			void move(production& src) {
				if (this == &src) return;
				symbol = src.symbol;
				priority = src.priority;
				name.move(src.name);              // charBuffer 目前按拷贝处理（无显式 move）
				assoc = src.assoc;
				assocL = src.assocL;
				content.move(src.content);    // vector 显式 move
			}
		};
		struct symbol
		{
			charBuffer name;// 它的名字，对应与nonterminal的下标
			vector<size_t> rules; // 由该非终结符号产生的所有产生式的下标
			
			symbol() : name(), rules() {}
			symbol(const symbol& rhs)
				: name(rhs.name), rules(rhs.rules) {
			}
			symbol& operator=(const symbol& rhs) {
				if (this != &rhs) {
					name = rhs.name;
					rules = rhs.rules;
				}
				return *this;
			}
			void move(symbol& src) {
				if (this == &src) return;
				name.move(src.name);
				rules.move(src.rules); // vector 显式 move
			}
		}; // 注意：补上分号
		enum ErrorCode
		{
			done = 0,
			undone = 1,
			unexpectedTernimal = 2,
			missingdivision = 3,
			missingRulesOrWrongSymbol = 4,
		};

		void demo(FILE* fp, const production & item) const;
		void demo(FILE* fp, const symbol& item) const;
		void demo(FILE* fp = stdout) const;

	private:
		ErrorCode ERROR;
		//size_t StartSymbol;  // 开始符（非终结符下标）
		//我们假定再输入结束后补充一个开始的增广文法 S' -> S 
		// 这个增广文法的开始符号是 "#all"，它的下标固定为 0
		//vector<charBuffer> nonterminal;//has length of count
		vector<charBuffer> terminal;
		vector<symbol> symbols;//has length of count of all symbols
		vector<production> rules;//has length of count of all rules

		vector < array < bool > > first;//matrix of symbols.count() * (nonterminal.count() + 1)
		vector < array < bool > > follow;//matrix of symbols.count() * (nonterminal.count() + 1)
	private:
		// —— 私有状态 —— 
		int check(void) const;
		void buildFirstFollow();
		// 若 symbols 尚未建立，则依 rules 聚合构建；可重复调用（幂等）

		// 先清空 first/follow 表，再按当前文法重建
		void buildFirst();
		void buildFollow();
		

		// —— 私有工具：索引/集合操作 —— 
		void ensureTablesSized_();     // 根据当前行列维度分配/清零 first/follow
		bool  setCell_(array<bool>& row, size_t col); // 置位并返回“是否有变化”
		bool  unionNoEps_(array<bool>& dst, const array<bool>& src); // 并集(不含 EPS 列)
		bool  unionFrom_(array<bool>& dst, const array<bool>& src, bool includeEps); // 并集，可选含 EPS


	}; 

	// 2) 在 class grammer 定义之后（同命名空间 hyperlex 内）添加 traits 专用化
	template<> struct is_bitwise_relocatable< grammer::production > { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like< grammer::production > { enum { value = 0 }; };
	template<> struct need_explicit_move< grammer::production > { enum { value = 1 }; };

	template<> struct is_bitwise_relocatable< grammer::symbol > { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like< grammer::symbol > { enum { value = 0 }; };
	template<> struct need_explicit_move< grammer::symbol > { enum { value = 1 }; };

	template<> struct is_bitwise_relocatable< grammer > { enum { value = 0 }; };
	template<> struct is_trivially_destructible_like< grammer > { enum { value = 0 }; };
	template<> struct need_explicit_move< grammer > { enum { value = 1 }; };

	class LR0
	{
	public:
		friend class grammer;
		// ==== 简化后的新 LR0 方法实现（放在 class LR0 声明之后）====
		inline LR0::LR0()
			: graph()
			, TerminalCount(0)
			, NonTerminalCount(0)
			, sheet()
			, Dstates()
		{
		}

		inline LR0::LR0(const LR0& G)
			: graph(G.graph)                  // dgraph 深拷贝
			, TerminalCount(G.TerminalCount)
			, NonTerminalCount(G.NonTerminalCount)
			, sheet(G.sheet)                  // vector 拷贝
			, Dstates(G.Dstates)
		{
		}

		inline LR0::~LR0()
		{
			// 若希望复用已分配 arena 块，可不 clear()；这里保守清空图结构
			graph.clear();
			graph.resetPoolsOwned();
			TerminalCount = 0;
			NonTerminalCount = 0;
			sheet.clear();
			Dstates.clear();
		}

		inline LR0& operator=(const LR0& G)
		{
			if (this == &G) return *this;
			graph = G.graph;                  // dgraph 拷贝赋值（独立副本）
			TerminalCount = G.TerminalCount;
			NonTerminalCount = G.NonTerminalCount;
			sheet = G.sheet;
			Dstates = G.Dstates;
			return *this;
		}

		inline void move(LR0& src)
		{
			if (&src == this) return;
			graph.move(src.graph);            // 窃取 dgraph（含其内部 arena）
			TerminalCount = src.TerminalCount;
			NonTerminalCount = src.NonTerminalCount;
			sheet.move(src.sheet);
			Dstates.move(src.Dstates);

			src.TerminalCount = 0;
			src.NonTerminalCount = 0;
		}

		inline void clear()
		{
			graph.clear();
			graph.resetPoolsOwned();          // 让 arena 逻辑索引从 0 重新开始
			TerminalCount = 0;
			NonTerminalCount = 0;
			sheet.clear();
			Dstates.clear();
		}
		void Demo(FILE* fp, const grammer& G);
		int build(const grammer& G);
		struct item
		{
			size_t rules;
			size_t dot;
		};
		struct edge
		{
			bool epsilon;
			sint symbol;
		};
	private:
		dgraph<item, edge> graph;

		size_t TerminalCount;
		size_t NonTerminalCount;
		vector<array<int> > sheet;
		vector<array<bool> > Dstates;

	};


}

/*                下面是未经重构的旧代码     */
/*计划开发 的类

1 NFA
2 DFA
3 Regex
4 Grammar
5 LR0
6 LR1
7 LRTable
8 AST
9 TokenStream

*/

namespace hyperlex
{
	template <class T> class tree
	{
	public:
		tree();
		~tree();
		void clear(void);
		void append(tree<T>* rear);
		void AppendChilds(tree<T>* ruined);
		void build(vector<tree<T>*>& input);
		void build(vector<tree<T>*>& input, size_t offset);
		void PostOrderTraversal(vector<tree<T>*>& output);
		inline T& root(void) { return content; }
		inline T const & root(void) const {return content;}
		size_t ChildCount(void) const;
		inline tree<T>* child(size_t No) const {return childs[No];}
		struct Iterator
		{
			tree<T>* target;
			int state;
		};
		class PostIterator
		{
		public:
			PostIterator() {}
			~PostIterator() {}
			void initial(tree<T>* root);
			int& state(void);
			tree<T>*& target(void);
			void next(void);
			bool still(void) const;
			inline void CutNow(void) const
			{
				stack.top().state = 1;
			}
		protected:
			vector<Iterator> stack;
			
		};
	private:
		vector<tree<T>*> childs;
		T content;
		tree<T>* parent;
		size_t No;
	};
	template <class T> class BiTree
	{
	public:
		BiTree();
		~BiTree();
		void clear(void);
		void build(BiTree<T>* left, BiTree<T>* right);
		void PreOrderTraversal(vector<BiTree<T>*>& output);
		void PreOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack);
		void InOrderTraversal(vector<BiTree<T>*>& output);
		void InOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack);
		void PostOrderTraversal(vector<BiTree<T>*>& output);
		void PostOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack);

		T& content(void);
		const T& content(void) const;
		BiTree<T>*& left(void);
		BiTree<T>*& right(void);
		void*& label(void);
		BiTree<T>* copy(void);
		struct Iterator
		{
			BiTree<T>* target;
			int state;
		};
		class iterator
		{
		public:
			iterator() {}
			~iterator() {}
			void initial(BiTree<T>* root);
			int& state(void);
			BiTree<T>*& target(void);
			void next(void);
			bool still(void);
		protected:
			vector<Iterator> stack;

		};
	private:
		BiTree<T>* Left;
		BiTree<T>* Right;
		void* tempLabel;
		T Content;
	};
	
}
namespace hyperlex
{
	template <class T> class list
	{
	private:
		size_t Count;
		size_t Size;
		T* content;
	public:
		list();
		~list();
		void refresh(void);
		void refresh(size_t NewCount);
		void reshape(size_t NewSize);
		void renew(size_t NewSize);
		void append(const T& element);
		size_t SearchAppend(const T& element);
		size_t pop(T& element);
		void pop(void);
		size_t append(void);
		size_t size(void) const;
		size_t count(void) const;
		void swap(list<T>& other);
		const T* vector(void)const;
		T* vector(void);
		const T* vector(size_t offset)const;
		T* vector(size_t offset);
		const T& operator[](size_t target) const;
		T& operator[](size_t target);
		void value(const T& element);
		const T& top(void) const;
		T& top(void);
	};
	template <class T> class matlist
	{
		/*
		matlist(size_t column);
		column can not be 0.
		*/
	public:
		matlist(size_t column);
		matlist();
		~matlist();
		void refresh(void);
		void refresh(size_t column, size_t length);
		void refresh(size_t row, size_t column, size_t length);
		//void reshape(size_t NewSize);
		void append(const T* element);
		size_t SearchAdd(const T* element);
		//size_t pop(T* element);
		T* append(void);
		size_t column(void) const;
		size_t row(void) const;
		size_t length(void) const;
		void swap(matlist<T>& other);
		const T* operator[](size_t target) const;
		T* operator[](size_t target);
		void value(const T element);
	private:
		size_t Row;
		size_t Column;
		size_t Length;
		T* content;
	};
	template <class T> class vec
	{
	private:
		size_t Size;
		T* content;
	public:
		vec();
		~vec();
		size_t size(void) const;
		T* vector(void);
		T& operator[](size_t target);
		T& operator[](const size_t target) const;
		void Malloc(size_t NewSize);
		void Realloc(size_t NewSize);
		void Free(void);
	};
	template <class Cg, class Ca> class Dgraph
	{
	public:
		struct vortex
		{
			size_t first;
			size_t rear;
			Cg content;
		};
		struct arc
		{
			size_t from;
			size_t to;
			size_t next;
			Ca content;
		};
		list<vortex> vertice;
		buffer<arc> arcs;
		Dgraph();
		~Dgraph();
		Cg& operator[](size_t target);
		void refresh(void);
		void refresh(size_t newlength);
		size_t FirstArc(size_t) const;
		size_t NextArc(size_t) const;
		size_t ArcTo(size_t) const;
		size_t ArcCount(size_t) const;
		size_t append(size_t from, size_t to, const Ca & C);
		void append(const Dgraph<Cg, Ca>& right, size_t VerticeOffset);
		void Demo(FILE* fp) const;
	};
}
namespace hyperlex
{
	class NFA;
	class sNFA;
	class sheetDFA;
	class DFA;
	//class lexicalPanel;
	class grammerS;
	class LR0;
	class LR1;
	class Gsheet;
}
// input analysis and lexical analysis.
namespace hyperlex
{
	class Morpheme;
	class GrammarTree;
	
	
	class GrammarTree
	{
	public:
		GrammarTree();
		~GrammarTree();
		struct TreeInfor
		{
			bool implicit;
			bool rules;
			size_t site;
			size_t label;
			void* infor;
			TreeInfor(void);
			// rules:false, this is a leaf node, and its a node corresponding to
			// a lexical terminal symbol then site is a location of the lexical unit 
			// in the lexical sheet
			// rules: true, this may be not a leaf node, 
			// site is the corresponding production rules
		};
		enum GrammarError 
		{
			NoError = 0,
			Undone,
			ActionError,
			GotoError,
			UnExpectEnd
		};
		//template<typename T> int build(const char* reg);
		void Demo(FILE* fp, const Morpheme& input, const char* const* RulesName) const;
		void clear(void);
		template<typename T> int build(const Morpheme& input);

		tree<TreeInfor>* GT;
		//error_record00 =  ture error infor from ACTION, otherwise from the sheet GOTO
		//error_record01 = lexical unit number;
		//error_record02 = (size_t)top content of stack;
		GrammarError error_record00;
		size_t error_record01;
		size_t error_record02;
	protected:
	};
	class Morpheme
	{
		/**
		* Structure storing lexical analysis results
		* @struct result
		* @member accept   the lexical unit is identified as
		* @member category Lexical category identifier
		* @member length   Length of matched lexical unit
		* @member begin    Starting position in input stream
		*/
	public:
		struct result
		{
			int accept;
			int category;
			size_t length;
			size_t begin;
			bool valid;
			size_t line;
			size_t file;
		};
		Morpheme();
		~Morpheme();
		char* Copy(size_t site) const;
		void append(const charBuffer& input, int accept, int category);
		void append(const char* fileName);
		void AppendEnd(int TerminalCount);
		void UnitMove(size_t from, size_t to);
		void CountReset(size_t count);
		void Demo(FILE* fp) const;
		size_t GetCount(void) const;
		const char* GetWord(size_t site) const;
		inline result const& operator[](const size_t target) const
		{
			return lex[target];
		}
		inline result const& operator[](const tree<GrammarTree::TreeInfor>* target) const
		{
			return lex[target->root().site];
		}
		char GetChar(size_t site) const;
		double GetReal(size_t site) const;
		long int GetInt(size_t site) const;
		char* GetString(size_t site) const;
		char* GetHeader(size_t site) const;
		bool& valid(size_t site);

		void insert(size_t from, size_t deleted, const Morpheme& src);
		void SetFile(size_t value);
		const char* GetFile(size_t value) const;
		size_t FileCount(void) const;
		void shrink(void);
		void sort(void);
		bool withTernimal(void)const;
		template<typename T> size_t Build(const char* reg);
		template<typename T> size_t Build(FILE* fp);
		template<typename T> size_t Build(const Morpheme& src);
		//size_t index;
		void clear(void);
		void ruin(void);
		void copy(const Morpheme& source);

		size_t initial(void) const;
		size_t next(size_t index) const;
		bool still(size_t index) const;
		int accept(size_t index) const;
		struct indexT
		{
			size_t UnitOffest;
			size_t CharOffset;
			inline indexT()
			{
				UnitOffest = 0;
				CharOffset = 0;
			}
		};
		
		void print(charBuffer & output) const;
		bool dequeue(char &out, indexT& index) const;
		void backspace(indexT& index, size_t count) const;
		bool operator==(const Morpheme& source) const;
	protected:
		size_t count;
		/*为了文法分析的便利性，
		最后一个符号必须是文件终止符号。在任意的词法单元编码规则下，
		文件终止符号和文件终止符号的种类对应的整数0。
		有点类似于C语言的字符串编码方式*/

		/*
		For the convenience of grammatical analysis, 
		the last symbol must be a ​​file terminator​​. 
		Under any lexical unit encoding rules, 
		the integer corresponding to the ​​file terminator​​ and its category is 
		​​0​​, similar to the string encoding method in the C language.
		*/

		//list<size_t> begin;
		//list<size_t> length;
		vector<const char*> SrcFile;
		vector<result> lex;
		vector<char> storage;

		void SetLine(void);
		size_t CountEnter(const char* unit);

		template<typename T> bool RunBuild(int& accept, charBuffer& result, charBuffer& input, charBuffer& intermediate);
		template<typename T> bool RunBuild(int& accept, charBuffer& result, const Morpheme& src, charBuffer& intermediate, indexT & index);
	};
	class RegularExp
	{
	public:
		RegularExp();
		~RegularExp();
		enum NodeType
		{
			Concatenation = 0,
			Alternation = 1,
			ZeroOrMore = 2,
			OneOrMore = 3,
			ZeroOrOne = 4,
			Range = 5,
		};
		struct item
		{
			int lower;
			int upper;
			NodeType type;
			void Demo(FILE* fp);
			void copy(const item& source);
		};

		void Demo(FILE* fp) const;
		static void Demo(FILE* fp, NodeType T);
		static void Demo(FILE* fp, int L, int U);
		void clear(void);

		int set(const char* input);

		void copy(RegularExp& source);
		void set(int L, int U);
		void set(int leaf);
		void set(BiTree<item>* reg);
		void set(BiTree<item>* reg, NodeType T);
		void set(BiTree<item>* regL, BiTree<item>* regR, NodeType T);
		void set(RegularExp* reg);
		void set(RegularExp* reg, NodeType T);
		void set(RegularExp* regL, RegularExp* regR, NodeType T);
		void set(RegularExp* regL, RegularExp* regR);
		void set(const Morpheme& eme, hyperlex::tree<GrammarTree::TreeInfor>* Tree);
		friend class sNFA;
	private:
		BiTree<item>* tree;
		void set(void);
		int fastBuild(Morpheme& eme);
		int standardBuild(Morpheme& eme);
	};
	class InputPanel
	{
	public:
		typedef const vector<const char*> cvccp;
		InputPanel();
		~InputPanel();
		
		int build_v02(const char* file);
		int build(FILE* fp);
		int build(const char* input);
		void demo(FILE* fp) const;
		void ErrorDemo(FILE* fp) const;
		int printL(FILE* fp, const char* nameL)const;
		int printG(FILE* output, FILE* infor, const char* nameG)const;

		struct RegContent
		{
			const char* name;
			long int priority;
			long int accept;
			size_t group; 
			//When two distinct regular expressions match simultaneously, 
			//the regular expression with the higher priority number is accepted.
			RegularExp* reg;
			RegContent();
			~RegContent();
			void SetName(const char* input);
		};
		struct RegGroup
		{
			const char* name;
			int priority;
			vector<RegContent*> regs;
			size_t prefix;
			RegGroup();
			~RegGroup();
			void SetName(const char* input);
		};
		struct Rules
		{
			const char* name;
			vector<long int> formula;
			bool implicit;
			Rules();
			~Rules();
			void SetName(const char* input);
			void demo(FILE* fp, cvccp& N, cvccp& T);
		};
		struct Group
		{
			size_t group;
			const char* name;
			vector<Rules*> rules;
			size_t count;
			size_t offset;
			bool implicit;
			Group();
			~Group();
			void SetName(const char* input);

		};
		enum errorType
		{
			NoError = 0,
			ConflictRegGroupName = 1,
			repeatRegName = 2,
			missingId = 3,
			repeatGGroupName = 4,
			repeatGName = 5,
			ErrorNonTernimal,
			WorngRuleBody,
			missingIdinRegdef,
			ErrorinputLEXICAL,
			PretreatLEXICAL,
			PretreatGRAMMAR,
			PretreatRepeat,
			PretreatOpenfail,
			ErrorinputGrammar,
			regGroupMissing,
			buildUndone,
		};
		friend class NFA;
		friend class grammerS;
	private:
		typedef hyperlex::tree<GrammarTree::TreeInfor> GLTree;
		typedef hyperlex::tree<GrammarTree::TreeInfor>::PostIterator GTIter;
		bool GrammarEnclosed;
		vector<RegGroup*> RegG;
		vector<RegContent*> regular;
		vector<Group*> GrammarG;

		vector<const char*> Terminal;
		vector<const char*> NontTerminal;
		char* RootName;

		vector<Rules*> rules;

		errorType errorCode;
		size_t errorInfor1;
		size_t errorInfor2;
		const char* errorInfor3;
		bool errorInfor4;

		Morpheme MorphemePre;
		Morpheme LexicalSource;

		int pretreatment(const char* input, Morpheme& output);

		void initial(void);
		void clear(void);
		/*
		demo of input file analysis;
		*/
		void demoL(FILE* fp) const;
		void demoG(FILE* fp) const;
		void printGName(FILE* output, FILE* infor, const char* nameG)const;
		void printImplicit(FILE* output, FILE* infor, const char* nameG)const;
		/*
		* input analysis;
		*/
		int buildGanalysis(const Morpheme& eme);
		int buildAll(const Morpheme& eme, GrammarTree& Tree);
		void buildLpost(void);

		int buildL(const Morpheme& eme, GLTree* Tree);
		void addVoidGroup(void);
		int RegGroupName(size_t& siteReturn, const Morpheme& eme, GLTree* Tree);
		int RegName(size_t& siteReturn, size_t group, const Morpheme& eme, GLTree* Tree);
		bool RegSearch(size_t& group, size_t& site, const char* name);
		int RegBuild(size_t siteReturn, size_t group, const Morpheme& eme, GLTree* Tree);
		void NeglectNullToken(Morpheme& eme) const;

		int buildG(const Morpheme& eme, GLTree* Tree);
		int buildRules(const Morpheme& eme, GLTree* Tree);
		void addAllGroup(void);
		void addAllGroup02(void);
		int GrammarGroup(size_t& GroupSite, const Morpheme& eme, GLTree* Tree);
		int RulesAppend(size_t GroupSite, GLTree* Name, const Morpheme& eme, GLTree* Tree);
		long int UnitToSymbol(GLTree* Tree, const Morpheme& eme);
		long int WildcardToSymbol(long int symbol, const Morpheme& eme, bool plus);
		void addTerminal(void);
		long int SymbolAdd(const char* symbol);
		long int UnitRegGroupAdd(const char* symbol);
		int NonTerminalSort(void);
		void ImplicitAdd(void);
	};

}

// lexical analysis

namespace hyperlex
{
	
	class ShrinkList
	{
	public:
		friend class sheetDFA;
		friend class DFA;
		ShrinkList(size_t AcceptCount, size_t size);
		~ShrinkList();
		void Insert(size_t site, size_t state);
		size_t DeleteNext(size_t now);
		size_t NewState(size_t Now);
		size_t Head(size_t site)const;
		size_t Count(void)const;
		void Demo(FILE* fp)const;
	private:
		vec<size_t> group;
		vec<size_t> next;
		size_t Statecount;
		list<size_t> head;
		list<size_t> rear;
	};
	struct Convert
	{
		char upper;
		char lower;
		bool epsilon;
		bool in(const char ele);
	};
	struct convert
	{
		int upper;
		int lower;
		//size_t to;
		bool in(const char ele);
		bool in(int ele);
	};
	class sNFA
	{
	public:
		friend class NFA;
		sNFA();
		~sNFA();
		//typedef buffer<Convert> converts;
		void refresh(void);
		void build(const RegularExp* Reg);

		//void build(const RegTree* Reg);
		//void build(const RegTree *Reg, buffer<size_t> &output, list<size_t>& s, list<sNFA*> &nfa);
		
		void Demo(FILE* fp) const;
	protected:
		void build(void);
		void build(const bool input[128]);
		void parallel(const sNFA& left, const sNFA& right);
		void serial(const sNFA& left, const sNFA& right);
		void any(const sNFA& right);
		void plus(const sNFA& right);
		void ZeroOrOne(const sNFA& right);

		void parallel(const sNFA* left, const sNFA* right);
		void serial(const sNFA* left, const sNFA* right);
		void any(const sNFA* right);
		void plus(const sNFA* right);
		void ZeroOrOne(const sNFA* right);
	private:
		Dgraph<int, Convert> graph;
		// content of vertice of graph is meanless
		// state = 0 is the begin
		size_t StateAmount;
		//DirectedGraph graph;
		size_t accepted;
		//converts CC;
	};
	class NFA
	{
	public:
		friend class sheetDFA;
		NFA(const sNFA& single);
		NFA(const sNFA* const* multiple, size_t count);
		//NFA(const lexicalPanel&lP);
		NFA(const InputPanel& lP);
		~NFA();
		void initial(bool* state, list<size_t>& stack) const;
		void closure(bool* state, list<size_t> &stack) const;
		size_t move(const bool* from, bool* to, const char ele, list<size_t>& stack) const;
		size_t GetAccepted(const bool* state, bool* accept) const;
		size_t FirstAccepted(const bool* accept) const;
		void Demo(FILE* fp) const;
	private:
		// content of vertice of graph is label of accpet
		// state = 0 is the begin
		// No i accepted state has graph.vertice[??].content = i
		Dgraph<int, Convert> graph;
		size_t StateAmount;
		size_t accepted;
		list<size_t> priority;
	private:
		void build(const sNFA* const* multiple, size_t count);
		//vec<bool> state;
	};
	class sheetDFA
	{
	public:
		friend class DFA;
		sheetDFA(const NFA & nfa);
		~sheetDFA();
		void shrink(void);
		bool ifDeadAccept(void)const;
		int next(int state, const char c)const;
		int action(int state)const;
		
		void Demo(FILE*fp)const ;
		static void Demo(FILE* fp, const bool *state, size_t n);
	private:
		size_t count;
		size_t AcceptCount;
		size_t LiveAcceptCount;
		matlist<int> sheet;
		list<int> accept;
		//matlist<int> accept;
		void acceptSet(const matlist<bool>& Dstates, const NFA& nfa);
		void shrink(const ShrinkList* SL);
	};
	enum NodeType
	{
		Concatenation = 0,
		Alternation = 1,
		ZeroOrMore = 2,
		OneOrMore = 3,
		AnyOne = 4,
	};
	class DFA
	{
	public:
		DFA(const sheetDFA* dfa);
		~DFA();
		int next(int state, const char c)const;
		int action(int state)const;
		void Demo(FILE* fp)const;
		void Cprint(FILE* fp, const char* name)const;
		void CppPrint(FILE* fp, const char* name)const;
		void CprintAccept(FILE* fp, const char* name, const char** const category, const char** const accept)const;
		void CppPrintAccept(FILE* fp, const char* name, const char** const category, const char** const accept)const;

		static void Cprint(FILE* fp, convert& CC);
		static void Demo(FILE* fp, int L, int U);
		static void Demo(FILE* fp, convert &CC);

		size_t StateAmountGet(void) const;
		int GraphStateGet(const size_t site) const;
	private:
		Dgraph<int, convert> graph;
		size_t StateAmount;
		size_t AcceptCount;
		void CprintCore(FILE* fp, const char* name)const;
		void CprintAcceptCore(FILE* fp, const char* name, const char** const category, const char** const accept)const;
	};
}
namespace hyperlex
{
	template<typename T> size_t Morpheme::Build(FILE* fp)
	{
		charBuffer input;
		charBuffer result;
		charBuffer intermediate;
		int accept;
		int error = 0;
		char now;
		input << fp;
		ruin();

		while (RunBuild<T>(accept, result, input, intermediate))
		{
			if (accept != 0) append(result, accept, T::GroupGet(accept));
			else
			{
				input.dequeue(now);
				result.append(now);
				append(result, -1, -1);
				AppendEnd(0);
				SetLine();
				return count;
			}
		}
		AppendEnd(0);
		SetLine();
		return error;
	}
	template<typename T> size_t Morpheme::Build(const char* reg)
	{
		charBuffer input;
		charBuffer result;
		charBuffer intermediate;
		int accept;
		int error = 0;
		char now;
		ruin();
		input = reg;
		while (RunBuild<T>(accept, result, input, intermediate))
		{
			if (accept != 0) append(result, accept, T::GroupGet(accept));
			else
			{
				input.dequeue(now);
				result.append(now);
				append(result, -1, -1);
				AppendEnd(0);
				SetLine();
				return count;
			}
		}
		AppendEnd(0);
		SetLine();
		
		return error;
	}
	template<typename T> size_t Morpheme::Build(const Morpheme& src)
	{
		//charBuffer input;
		charBuffer result;
		charBuffer intermediate;
		int accept = 0;
		int error = 0;
		char now;
		indexT index;
		ruin();
		for (size_t i = 0; i < src.SrcFile.count(); i++)
		{
			append(src.SrcFile[i]);
		}
		size_t record = index.UnitOffest;
		while (RunBuild<T>(accept, result, src, intermediate, index))
		{
			//std::cout << "count: " << count << std::endl;
			//std::cout << "record: " << record << std::endl;
			//std::cout << "accept: " << accept << std::endl;
			//std::cout << "index.UnitOffest: " << index.UnitOffest << std::endl;
			//std::cout << "index.CharOffset: " << index.CharOffset << std::endl;
			if (accept != 0) append(result, accept, T::GroupGet(accept));
			else
			{
				src.backspace(index, 1);
				result.append(now);
				append(result, -1, -1);
				AppendEnd(0);
				SetLine();
				return count;
			}
			lex[count - 1].line = src.lex[record].line;
			lex[count - 1].file = src.lex[record].file;
			record = index.UnitOffest;
		}
		AppendEnd(0);
		return 0;
	}
	template<typename T> bool Morpheme::RunBuild(int& accept, charBuffer& result, charBuffer& input, charBuffer& intermediate)
	{
		/*
	example:
	1 aa
	2 aaBB
	3 Bcc
	input: aaBcc
	*/
		char now;
		//char cc;
		int state, acc;
		int action;
		intermediate.clear();
		state = 0;
		acc = 0;
		action = 0;
		accept = 0;
		result.clear();
		while (input.dequeue(now))
		{
			/*state switch*/
			/*change here to get a different automata*/
			state = T::next(state, now);
			acc = T::action(state);
			/*change here to get a different automata*/
			accept = acc != 0 ? acc : accept;
			switch (action)
			{
			case 0://initial
				if (state != 0 && acc == 0)
				{
					intermediate.append(now);
					action = 1;
				}
				else if (state != 0 && acc != 0)
				{
					result.append(now);
					action = 2;
				}
				else
				{
					input.backspace(now);
					return true;
				}
				break;
			case 1://run and waiting for accept
				if (state == 0)
				{
					input.backspace(now);
					input.backspace(intermediate);
					return true;
				}
				else if (acc != 0)
				{
					result.append(intermediate);
					result.append(now);
					intermediate.clear();
					action = 2;
				}
				else intermediate.append(now);//continue 
				break;
			case 2://accept
				if (state == 0)//accept
				{
					input.backspace(now);
					//accept = last;
					return true;
				}
				else if (acc == 0)
				{
					intermediate.append(now);
					action = 1;
				}
				else result.append(now);
				break;
			}
		}
		if (action == 1)
			input.backspace(intermediate);
		return action != 0;
	}
	template<typename T> bool Morpheme::RunBuild(int& accept, charBuffer& result, const Morpheme& src, charBuffer& intermediate, indexT& index)
	{
		/*
	example:
	1 aa
	2 aaBB
	3 Bcc
	input: aaBcc
	*/
		char now;
		//char cc;
		int state, acc;
		int action;
		indexT RecoverRecord;
		intermediate.clear();
		state = 0;
		acc = 0;
		action = 0;
		accept = 0;
		result.clear();
		RecoverRecord = index;
		while (src.dequeue(now, index))
		{
			/*state switch*/
			/*change here to get a different automata*/
			state = T::next(state, now);
			acc = T::action(state);
			/*change here to get a different automata*/
			accept = acc != 0 ? acc : accept;
			switch (action)
			{
			case 0://initial
				if (state != 0 && acc == 0)
				{
					intermediate.append(now);
					action = 1;
				}
				else if (state != 0 && acc != 0)
				{
					result.append(now);
					action = 2;
				}
				else
				{
					index = RecoverRecord;
					//input.backspace(now);
					return true;
				}
				break;
			case 1://run and waiting for accept
				if (state == 0)
				{
					index = RecoverRecord;
					//input.backspace(now);
					//input.backspace(intermediate);
					return true;
				}
				else if (acc != 0)
				{
					result.append(intermediate);
					result.append(now);
					intermediate.clear();
					action = 2;
				}
				else intermediate.append(now);//continue 
				break;
			case 2://accept
				if (state == 0)//accept
				{
					src.backspace(index, 1);
					//input.backspace(now);
					//accept = last;
					return true;
				}
				else if (acc == 0)
				{
					intermediate.append(now);
					action = 1;
				}
				else result.append(now);
				break;
			}
		}
		if (action == 1)
			src.backspace(index, intermediate.count());
			//input.backspace(intermediate);
		return action != 0;
	}
	
	
	template<typename T> int GrammarTree::build(const Morpheme& input)
	{
		vector<int> stack;
		vector<tree<TreeInfor>*> TempTree;
		tree<TreeInfor>* TreeNow, * TreeChild;
		bool DoNext;
		size_t length, head, i, begin_;// , inputCount_;
		int symbol, top, temp, information;
		int GoFull, GoD, GoI, error;
		typename T::type type;
		stack.append(0);
		head = input.initial();
		//inputCount_ = input.GetCount();
		DoNext = true;
		do
		{
			if (!input.still(head))
			{
				error = -1;
				error_record00 = GrammarTree::UnExpectEnd;
				error_record01 = head - 1;
				error_record02 = (size_t)top;
				break;
			}
			top = stack.top();
			temp = T::ACTION[top][input.accept(head)];
			information = temp / 4;
			type = (typename T::type)(temp % 4);
			//printf( "T = %5d, top = %5d, information = %5d, type = %5d, ", input[head].accept, top, information, (int)type);
			//printf("head = %5zu, lex = %s, \n", head, input.GetWord(head));
			switch (type)
			{
			case T::accept:
				error = 0;
				DoNext = false;
				clear();
				begin_ = TempTree.count() - 1;
				TreeNow = new tree<TreeInfor>;
				TreeNow->root().implicit = false;
				TreeNow->root().rules = true;
				TreeNow->root().site = 0;
				TreeNow->root().infor = NULL;
				TreeNow->build(TempTree, begin_);
				TempTree.pop();
				GT = TreeNow;
				//TempTree.pop(GT);
				break;
			case T::error:
				error_record00 = GrammarTree::ActionError;
				error_record01 = head;
				error_record02 = (size_t)top;
				//printf("error_record01: %zu\n", error_record01);
				//printf("error_record02: %zu\n", error_record02);
				error = temp;
				DoNext = false;
				break;
			case T::push:
				
				//printf("<%8zu, %4d: %4d , %s>\n", head, input[head].category, input[head].accept, input.GetWord(head));
				stack.append(information);
				TreeNow = new tree<TreeInfor>;
				TreeNow->root().implicit = false;
				TreeNow->root().rules = false;
				TreeNow->root().site = head;
				TreeNow->root().infor = NULL;
				TempTree.append(TreeNow);		
				head = input.next(head);
				
				break;
			case T::reduce:
				symbol = T::RulesToSymbol[information];
				length = T::RulesLength[information];
				begin_ = TempTree.count() - length;

				TreeNow = new tree<TreeInfor>;
				TreeNow->root().implicit = (bool)T::Implicit[(size_t)information];
				TreeNow->root().rules = true;
				TreeNow->root().site = information;
				TreeNow->root().infor = NULL;
				//TreeNow->build(TempTree, begin_);
				
				for (i = 0; i < length; i++)
				{
					stack.pop();
					TreeChild = TempTree[begin_ + i];
					if (TreeChild->root().implicit)
						TreeNow->AppendChilds(TreeChild);
					else TreeNow->append(TreeChild);
					TempTree[begin_ + i] = NULL;
				}
				TempTree.recount(begin_);
				GoFull = T::GOTO[stack.top()][symbol];
				GoD = GoFull / 4;
				GoI = GoFull % 4;
				//printf("<%6d: %6d, %6d>\n", GoFull, GoD, GoI);
				if ((typename T::type)GoI == T::push)
				{
					stack.append(GoD);
					TempTree.append(TreeNow);
				}
				else
				{
					error_record00 = GrammarTree::GotoError;
					error_record01 = head;
					error_record02 = (size_t)top;
					error = GoFull;
					DoNext = false;
				}
				break;
			}

		} while (DoNext);

		for (i = 0; i < TempTree.count(); i++)
		{
			//printf("<%8zu>\n", i);
			if (TempTree[i] != NULL)
			{
				//printf("####\n");
				TempTree[i]->clear();
				delete TempTree[i];
			}
		}
		return error;
	}

}
// grammer analysis
namespace hyperlex
{
	class grammerS
	{
	public:
		friend class LR0;
		friend class LR1;
		friend class Gsheet;
		grammerS();
		~grammerS();
		int build(const InputPanel& input);
		int build(FILE* fp);
		int build(charBuffer& input);
		void Demo(FILE* fp) const;
		void Cprint(FILE* fp) const;
		void Demo(FILE* fp, size_t rule) const;
		void Demo(FILE* fp, size_t rule, size_t dot) const;
		const char* SymbolGet(long long int index) const;
		const long long int* vector(size_t No)const;
		void SetExample(void);
		struct production
		{
			size_t symbol;
			size_t length;
			size_t begin;
			size_t LengthWithoutVoid;
		};
		enum ErrorCode
		{
			done = 0,
			undone = 1,
			unexpectedTernimal = 2,
			missingdivision = 3,
			missingRulesOrWrongSymbol = 4,
		};
	private:
		ErrorCode ERROR;
		size_t count;// count of non-terminal
		size_t TerminalCount;
		//[0,count-1] non-terminal
		//[count,TerminalCount + count -1]; terminal
		//TerminalCount + count: epsilon
		//TerminalCount + count + 1: END-EOF
		long long int epsilon;
		long long int end;
		list<size_t> degeneracy;//has length of count.
		//degeneracy[i]: rules' count of non-terminal[i]
		list<size_t> prefix;//has length of count
		//prefix[i]: rules' begining index of non-terminal[i]
		list<const char*> name;//has length of count
		list<const char*> ternimal;
		list<production> rules;//has length of count of all rules
		list<long long int> all;//Production Rules

		matlist<bool> first;//matrix of count * (TerminalCount + 2)
		matlist<bool> follow;//matrix of count * (TerminalCount + 2)
	private:
		void append(const char* input);
		void Tappend(const char* input);
		size_t SearchAppend(const char* input);
		long long int SearchTerminal(const char* input);
		int nextTest(int state, const char c);
		int actionTest(int state);
		bool RunBuild(int&accept, charBuffer& result, charBuffer& input, charBuffer& intermediate);
	private:
		
		void FirstBiuld(void);
		bool IfEpsilon(long long int site) const;
		bool FirstOr(long long int symbol, bool* to) const;
		bool Or(const bool* from, bool* to) const;
		bool FollowOr(const bool* from, size_t to);
		bool AddFirstBeta(bool* result, size_t L, const long long int* in) const;
		void FirstBeta(bool* result, size_t L, const long long int*in) const;
		void FollowBiuld(void);
	};
	template <class Cg> class LRNFA
	{
	public:
		struct vortex
		{
			size_t first;
			size_t rear;
			Cg content;
		};
		struct arc
		{
			size_t from;
			size_t to;
			size_t next;
			bool epsilon;
			long long int symbol;
			//bool in(long long int ele);
		};
		list<vortex> vertice;
		buffer<arc> arcs;
		LRNFA();
		~LRNFA();
		Cg& operator[](size_t target);
		const Cg& operator[](size_t target) const;
		void refresh(void);
		void refresh(size_t newlength);
		size_t VortexAppend(const Cg& element);
		size_t FirstArc(size_t) const;
		size_t NextArc(size_t) const;
		size_t ArcTo(size_t) const;
		size_t ArcCount(size_t) const;
		size_t append(size_t from, size_t to, bool Epsilon, long long int Symbol);
		void Demo(FILE* fp) const;

		void initial(bool* state, list<size_t>& stack) const;
		void closure(bool* state, list<size_t>& stack) const;
		size_t move(const bool* from, bool* to, long long int ele, list<size_t>& stack) const;
		void build(matlist<int>& sheet, matlist<bool> &Dstates, size_t NonTcount, size_t Tcount) const;
	};
	class LR0
	{
	public:
		friend class Gsheet;
		LR0(const grammerS *G);
		~LR0();
		void Demo(FILE*fp, const grammerS* G);
		struct item
		{
			size_t rules;
			size_t dot;
		};
	private:
		LRNFA<item> graph;

		size_t TerminalCount;
		size_t NonTerminalCount;
		matlist<int> sheet;
		matlist<bool> Dstates;
		//void build(const grammerS* G);
		
	};
	class LR1
	{
	public:
		friend class Gsheet;
		LR1(const grammerS* G);
		~LR1();
		void Demo(FILE* fp, const grammerS* G);
		void Demo(FILE* fp, size_t site, const grammerS* G);
		struct item
		{
			size_t rules;
			size_t dot;
			long long int symbol;
			bool operator==(const item R) const;
		};
	private:
		LRNFA<item> graph;

		size_t TerminalCount;
		size_t NonTerminalCount;
		matlist<int> sheet;
		matlist<bool> Dstates;
		size_t SearchAppend(const item& I, bool& IfAppend);
		//void build(const grammerS* G);
	};
	class Gsheet
	{
	public:
		Gsheet();
		~Gsheet();
		enum type
		{
			accept = 0,
			error = 1,
			push = 2,
			reduce = 3,
		};
		struct infor
		{
			type action;
			int state;
		};
		enum ErrorType
		{
			NoError = 0,
			uninitialized = 1,
			ConflictACTION = 2,
			ConflictGOTO = 3,
		};
		struct ErrorInfor
		{
			size_t i;
			size_t j;
			type ActionOld;
			int StateOld;
			type ActionNew;
			int StateNew;
		};
		void build(const LR0* lr, const grammerS* G);
		void build(const LR1* lr, const grammerS* G);
		int build(const matlist<int>& sheet, const matlist<bool>& Dstates, const grammerS* G);
		void build(void);//after
		void Demo(FILE* fp) const;
		void Demo(FILE* fp, const LR0* lr, const grammerS* G)const;
		void Demo(FILE* fp, const LR1* lr, const grammerS* G)const;

		infor Goto(size_t state, size_t symbol) const;
		infor Action(size_t state, size_t symbol) const;
		int GetSymbol(size_t rules) const;
		void Cprint(const char* name, FILE* fp)const;
		void CppPrint(const char* name, FILE* fp)const;
		void CppStructPrint(const char* name, FILE* fp, const grammerS * grammer)const;
		void CppStructPrint01(const char* name, FILE* fp, const grammerS* grammer)const;
		void CppStructPrint02(const char* name, FILE* fp, const grammerS* grammer)const;
		// now site 0 is END-EOF, site 1-N Are N terminal symbol
		static const char* TypeToChar(type TT);
		ErrorType ErrorTypeGet(void);
		ErrorInfor ErrorInforGet(void);
	private:
		size_t StateCount;
		size_t TerminalCount;
		size_t NonTerminalCount;
		size_t RulesCount;

		infor* ACTION;
		infor* GOTO;
		int* RulesToSmbol;
		int* RulesLength;

		ErrorType ET;
		ErrorInfor EI;

		void build_singleErrorAdd(void);

		bool gotoAdd(size_t i, size_t j, type Action, int State);
		bool actionAdd(size_t i, size_t j, type Action, int State);
		bool gotoCheck(size_t i, size_t j);
		bool actionCheck(size_t i, size_t j);
		void Demo01(FILE* fp)const;
		void Demo02(FILE* fp)const;
		void Demo03(FILE* fp)const;

		//void CppStructPrint01(const char* name, FILE* fp, const grammerS* grammer)const;
		//void CppStructPrint02(const char* name, FILE* fp, const grammerS* grammer)const;
	};
}
#define SizeMax ((size_t)0xffffffffffffffff)
#define CharSize ((size_t)(1 << (sizeof(char) * 8 - 1)))


#include<stdlib.h>
namespace hyperlex
{

	template <class T> tree<T>::tree()
	{
		parent = NULL;
		No = 0;
	}
	template <class T> tree<T>::~tree()
	{
	}
	template <class T> void tree<T>::clear(void)
	{
		vector<tree<T>*> deleted;
		size_t i;
		PostOrderTraversal(deleted);
		for (i = 1; i < deleted.count(); i++)
			delete deleted[i - 1];
		childs.recapacity(0);
	}
	template <class T> void tree<T>::PostOrderTraversal(vector<tree<T>*>& output)
	{
		vector<bool> StackState;
		vector<tree<T>*> StackSite;
		tree<T>* here;
		bool label;
		size_t i;
		for (i = childs.count(); i != 0; i--)
		{
			StackSite.append(childs[i - 1]);
			StackState.append(false);
		}
		while (StackState.pop(label) != 0)
		{
			StackSite.pop(here);
			if (here == NULL) continue;
			if (label) output.append(here);
			else
			{
				StackSite.append(here);
				StackState.append(true);

				for (i = here->childs.count(); i != 0; i--)
				{
					StackSite.append(here->childs[i - 1]);
					StackState.append(false);
				}
			}
		}
		output.append((tree<T>*)this);
	}
	template <class T> void tree<T>::append(tree<T>* rear)
	{
		childs.append(rear);
		rear->parent = this;
		rear->No = childs.count() - 1;
	}
	template <class T> void tree<T>::AppendChilds(tree<T>* ruined)
	{
		size_t i;
		tree<T>* rear;
		for (i = 0; i < ruined->ChildCount(); i++)
		{
			rear = ruined->child(i);
			childs.append(rear);
			rear->parent = this;
			rear->No = childs.count() - 1;
		}
		ruined->childs.clear();
		delete ruined;
	}
	template <class T> void tree<T>::build(vector<tree<T>*>& input)
	{
		size_t i;
		childs.recount(input.count());
		for (i = 0; i < input.count(); i++)
		{
			childs[i] = input[i];
			childs[i]->parent = this;
			childs[i]->No = i;
		}
	}
	template <class T> void tree<T>::build(vector<tree<T>*>& input, size_t offset)
	{
		size_t i;
		if (input.count() <= offset)
		{
			childs.recount(0);
			return;
		}
		childs.recount(input.count() - offset);
		for (i = 0; i < input.count() - offset; i++)
		{
			childs[i] = input[i + offset];
			childs[i]->parent = this;
			childs[i]->No = i;
		}
	}

	template <class T> size_t tree<T>::ChildCount(void) const
	{
		return childs.count();
	}

	template <class T> int& tree<T>::PostIterator::state(void)
	{
		return stack.top().state;
	}
	template <class T> tree<T>*& tree<T>::PostIterator::target(void)
	{
		return stack.top().target;
	}
	template <class T> void tree<T>::PostIterator::initial(tree<T>* root)
	{
		Iterator now;
		stack.clear();
		if (root != NULL)
		{
			now.state = 0;
			now.target = root;
			stack.append(now);
		}
	}
	template <class T> void tree<T>::PostIterator::next(void)
	{
		size_t i; 
		Iterator now, parent;
		tree<T>* here;
		if (stack.pop(parent) != 0)
		{
			if (parent.state == 0)
			{
				parent.state = 1;
				stack.append(parent);
				here = parent.target;
				now.state = 0;
				for (i = here->childs.count(); i != 0; i--)
				{
					now.target = here->childs[i - 1];
					stack.append(now);
				}
			}
		}
		
	}
	template <class T> bool tree<T>::PostIterator::still(void) const
	{
		return stack.count() != 0;
	}


	template <class T> BiTree<T>::BiTree()
	{
		Left = NULL;
		Right = NULL;
		tempLabel = NULL;
	}
	template <class T> BiTree<T>::~BiTree()
	{
		Left = NULL;
		Right = NULL;
	}
	template <class T> int& BiTree<T>::iterator::state(void)
	{
		return stack.top().state;
	}
	template <class T> BiTree<T>*& BiTree<T>::iterator::target(void)
	{
		return stack.top().target;
	}
	template <class T> void BiTree<T>::iterator::initial(BiTree<T>* root)
	{
		Iterator now;
		stack.clear();
		if (root != NULL)
		{
			now.state = 0;
			now.target = root;
			stack.append(now);
		}
	}
	template <class T> void BiTree<T>::iterator::next(void)
	{
		size_t i;
		Iterator now, parent;
		now.state = 0;
		if (stack.pop(parent) != 0)
		{
			if (parent.state == 0)
			{
				parent.state = 2;
				stack.append(parent);
				if (parent.target->Right != NULL)
				{
					now.target = parent.target->Right;
					stack.append(now);
				}
				parent.state = 1;
				stack.append(parent);
				if (parent.target->Left != NULL)
				{
					now.target = parent.target->Left;
					stack.append(now);
				}
			}
		}

	}
	template <class T> bool BiTree<T>::iterator::still(void)
	{
		return stack.count() != 0;
	}

	template <class T> void BiTree<T>::clear(void)
	{
		vector<BiTree<T>*> output;
		size_t i;
		PostOrderTraversal(output);
		for (i = 1; i < output.count(); i++) delete output[i - 1];
		Left = NULL;
		Right = NULL;
	}
	template <class T> BiTree<T>* BiTree<T>::copy(void)
	{
		vector<BiTree<T>*> output;
		size_t i;
		BiTree<T>* now, *temp;
		PostOrderTraversal(output);
		for (i = 0; i < output.count(); i++)
		{
			now = output[i];
			temp = new BiTree<T>;
			temp->Content.copy(now->Content);
			if (now->Left != NULL)
			{
				temp->Left = (BiTree<T>*)now->Left->tempLabel;
				now->Left->tempLabel = NULL;
			}
			if (now->Right != NULL)
			{
				temp->Right = (BiTree<T>*)now->Right->tempLabel;
				now->Right->tempLabel = NULL;
			}
			now->tempLabel = (void*)temp;
		}
		now = (BiTree<T>*)tempLabel;
		tempLabel = NULL;
		return now;
	}
	template <class T> void BiTree<T>::build(BiTree<T>* left_, BiTree<T>* right_)
	{
		Left = left_;
		Right = right_;
	}
	template <class T> T& BiTree<T>::content(void)
	{
		return Content;
	}
	template <class T> const T& BiTree<T>::content(void) const
	{
		return Content;
	}
	template <class T> BiTree<T>*& BiTree<T>::left(void)
	{
		return Left;
	}
	template <class T> BiTree<T>*& BiTree<T>::right(void)
	{
		return Right;
	}
	template <class T> void*& BiTree<T>::label(void)
	{
		return tempLabel;
	}
	template <class T> void BiTree<T>::PreOrderTraversal(vector<BiTree<T>*>& output)
	{
		vector<BiTree<T>*> stack;
		PreOrderTraversal(output, stack);
	}
	template <class T> void BiTree<T>::PreOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack)
	{
		BiTree<T>* now;
		stack.clear();
		stack.append(this);
		while (stack.pop(now) != 0)
		{
			if (now != NULL)
			{
				output.append(now);
				stack.append(now->Right);
				stack.append(now->Left);
			}
		}
	}
	template <class T> void BiTree<T>::InOrderTraversal(vector<BiTree<T>*>& output)
	{
		vector<BiTree<T>*> stack;
		InOrderTraversal(output, stack);
	}
	template <class T> void BiTree<T>::InOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack)
	{
		BiTree<T>* now;
		stack.clear();
		now = this;
		while (now != NULL || stack.count() != 0)
		{
			while (now != NULL)
			{
				stack.append(now);
				now = now->Left;
			}
			stack.pop(now);
			output.append(now);
			now = now->Right;
		}
	}
	template <class T> void BiTree<T>::PostOrderTraversal(vector<BiTree<T>*>& output)
	{
		vector<BiTree<T>*> stack;
		PostOrderTraversal(output, stack);
	}
	template <class T> void BiTree<T>::PostOrderTraversal(vector<BiTree<T>*>& output, vector<BiTree<T>*>& stack)
	{
		BiTree<T>* now;
		BiTree<T>* LeftMost, * LastOutput;
		stack.clear();
		now = this;
		LastOutput = NULL;
		while (now != NULL || stack.count() != 0)
		{
			while (now != NULL)
			{
				stack.append(now);
				now = now->Left;
			}
			LeftMost = stack.top();
			if (LeftMost->Right == NULL || LeftMost->Right == LastOutput)
			{
				output.append(LeftMost);
				LastOutput = LeftMost;
				stack.pop();
			}
			else
				now = LeftMost->Right;
		}
	}


}
namespace hyperlex
{
	template <class T> list<T>::list()
	{
		Count = 0;
		Size = 0;
		content = NULL;
	}
	template <class T> list<T>::~list()
	{
		Count = 0;
		Size = 0;
		free(content);
		content = NULL;
	}
	template <class T> void list<T>::append(const T& element)
	{
		size_t should;
		should = append();
		content[should] = element;
	}
	template <class T> size_t list<T>::SearchAppend(const T& element)
	{
		size_t i, j;
		const T* temp;
		for (i = 0; i < Count; i++)
		{
			if (content[i] == element) return i;
		}
		append(element);
		return Count - 1;
	}
	template <class T> void list<T>::refresh(void)
	{
		Count = 0;
	}
	template <class T> void list<T>::refresh(size_t NewCount)
	{
		content = (T*)realloc(content, NewCount * sizeof(T));
		Size = NewCount;
		Count = NewCount;
	}
	template <class T> void list<T>::renew(size_t NewCount)
	{
		if (NewCount > Size)
		{
			//std::cout <<"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<< std::endl;
			//std::cout << "NewCount: " << NewCount << "Size: " << Size << std::endl;
			//std::cout << "old content: " << content << std::endl;
			content = (T*)realloc(content, NewCount * sizeof(T));
			//std::cout << "new content: " << content << std::endl;
			Size = NewCount;
		}
		Count = NewCount;
	}
	template <class T> void list<T>::reshape(size_t NewSize)
	{
		if (NewSize <= Count) Count = NewSize;
		content = (T*)realloc(content, NewSize * sizeof(T));
		Size = NewSize;
	}
	template <class T> size_t list<T>::pop(T& element)
	{
		if (Count != 0)
		{
			Count -= 1;
			element = content[Count];
			return Count + 1;
		}
		return Count;
	}
	template <class T> void list<T>::pop(void)
	{
		if (Count != 0) Count -= 1;
	}
	template <class T> size_t list<T>::append(void)
	{
		size_t should, new_size;
		if (Count >= Size)
		{
			new_size = (Size + Size / 4 + 8);
			content = (T*)realloc(content, new_size * sizeof(T));
			Size = new_size;
		}
		should = Count;
		Count += 1;
		return should;
	}
	template <class T> size_t list<T>::count(void) const
	{
		return Count;
	}
	template <class T> size_t list<T>::size(void) const
	{
		return Size;
	}
	template <class T> void list<T>::swap(list<T>& other)
	{
		T* middle;
		middle = other.content;
		other.content = content;
		content = middle;

		size_t MM;

		MM = other.Count;
		other.Count = Count;
		Count = MM;

		MM = other.Size;
		other.Size = Size;
		Size = MM;
	}
	template <class T> const T* list<T>::vector(void)const
	{
		return content;
	}
	template <class T> T* list<T>::vector(void)
	{
		return content;
	}
	template <class T> const T* list<T>::vector(size_t offset)const
	{
		return content + offset;
	}
	template <class T> T* list<T>::vector(size_t offset)
	{
		return content + offset;
	}
	template <class T> const T& list<T>::operator[](size_t target) const
	{
		return content[target];
	}
	template <class T> T& list<T>::operator[](size_t target)
	{
		return content[target];
	}
	template <class T> void list<T>::value(const T& element)
	{
		size_t i;
		for (i = 0; i < Count; i++)
			content[i] = element;
	}
	template <class T> const T& list<T>::top(void) const
	{
		size_t target;
		target = Count != 0 ? Count - 1 : 0;
		return content[target];
	}
	template <class T> T& list<T>::top(void)
	{
		size_t target;
		target = Count != 0 ? Count - 1 : 0;
		return content[target];
	}


	template <class T> matlist<T>::matlist()
	{
		Row = 0;
		Column = 1;
		Length = 0;
		//fprintf(stdout, "matlist(): row(): %zu, column(): %zu,  length(): %zu.\n", Row, Column, Length);
		content = NULL;
	}
	template <class T> matlist<T>::matlist(size_t column)
	{
		Row = 0;
		Column = column;
		Length = 0;
		content = NULL;
	}
	template <class T> matlist<T>::~matlist()
	{
		Row = 0;
		Column = 0;
		Length = 0;
		free(content);
		content = NULL;
	}
	template <class T> void matlist<T>::refresh(void)
	{
		Row = 0;
	}
	template <class T> void matlist<T>::refresh(size_t row, size_t column, size_t length)
	{
		Row = row;
		Column = column;
		Length = length;
		//free(content);
		//fprintf(stdout, "refresh: row(): %zu, column(): %zu,  length(): %zu.\n", row, column, length);
		content = (T*)realloc(content, column * length * sizeof(T));
		//if(content == NULL) fprintf(stdout, "refresh: content == NULL.\n");
		//else fprintf(stdout, "refresh: content == %zu.\n", (size_t)content);
	}
	template <class T> void matlist<T>::refresh(size_t column, size_t length)
	{
		Row = 0;
		Column = column;
		Length = length;
		//free(content);
		content = (T*)realloc(content, column * length * sizeof(T));
	}
	template <class T> void matlist<T>::append(const T* element)
	{
		size_t i;
		T* line;
		line = append();
		for (i = 0; i < Column; i++) line[i] = element[i];

	}
	//size_t pop(T* element);
	template <class T> T* matlist<T>::append(void)
	{
		size_t should, new_size;
		if (Row >= Length)
		{
			new_size = (Length + Length / 4 + 8);
			content = (T*)realloc(content, Column * new_size * sizeof(T));
			Length = new_size;
			//std::cout << "content: " << content << ", new_size: " << new_size << "Row: " << Row << std::endl;
		}
		should = Row;
		Row += 1;
		return content + should * Column;
	}

	template <class T> size_t matlist<T>::SearchAdd(const T* element)
	{
		size_t i, j;
		const T* temp;
		for (i = 0; i < Row; i++)
		{
			temp = content + i * Column;
			for (j = 0; j < Column; j++)
				if (temp[j] != element[j]) break;
			if (j == Column) return i;
		}
		append(element);
		return Row - 1;
	}
	template <class T> size_t matlist<T>::column(void) const
	{
		return Column;
	}
	template <class T> size_t matlist<T>::row(void) const
	{
		return Row;
	}
	template <class T> size_t matlist<T>::length(void) const
	{
		return Length;
	}
	template <class T> void matlist<T>::swap(matlist<T>& other)
	{
		T* middle;
		middle = other.content;
		other.content = content;
		content = middle;

		size_t MM;

		MM = other.Column;
		other.Column = Column;
		Column = MM;

		MM = other.Row;
		other.Row = Row;
		Row = MM;

		MM = other.Length;
		other.Length = Length;
		Length = MM;
	}
	template <class T> const T* matlist<T>::operator[](size_t target) const
	{

		return content + target * Column;
	}
	template <class T> T* matlist<T>::operator[](size_t target)
	{
		//fprintf(stdout, "template <class T> T* matlist<T>::operator[](size_t target)\n");
		//fprintf(stdout, "target: %zu, Column: %zu, content: %zu\n", target, Column, (size_t)content);
		return content + target * Column;
	}
	template <class T> void matlist<T>::value(const T element)
	{
		size_t i;
		for (i = 0; i < Row * Column; i++)
		{
			content[i] = element;
		}
	}

	template <class T> vec<T>::vec()
	{
		Size = 0;
		content = NULL;
	}
	template <class T> vec<T>::~vec()
	{
		Size = 0;
		free(content);
		content = NULL;
	}
	template <class T> size_t vec<T>::size(void) const
	{
		return Size;
	}
	template <class T> T* vec<T>::vector(void)
	{
		return content;
	}
	template <class T> T& vec<T>::operator[](size_t target)
	{
		return content[target];
	}
	template <class T> T& vec<T>::operator[](const size_t target) const
	{
		return content[target];
	}
	template <class T> void vec<T>::Malloc(size_t NewSize)
	{
		Size = NewSize;
		content = (T*)malloc(NewSize * sizeof(T));
	}
	template <class T> void vec<T>::Realloc(size_t NewSize)
	{
		content = (T*)realloc(content, NewSize * sizeof(T));
		Size = NewSize;
	}
	template <class T> void vec<T>::Free(void)
	{
		Size = 0;
		free(content);
		content = NULL;
	}


}
namespace hyperlex
{
	template <class Cg, class Ca> Dgraph<Cg, Ca>::Dgraph()
	{

	}
	template <class Cg, class Ca> Dgraph<Cg, Ca>::~Dgraph()
	{

	}
	template <class Cg, class Ca> Cg& Dgraph<Cg, Ca>::operator[](size_t target)
	{
		return vertice.content[target].content;
	}
	template <class Cg, class Ca> void Dgraph<Cg, Ca>::refresh(void)
	{
		vertice.refresh();
		arcs.clear();
	}
	template <class Cg, class Ca> void Dgraph<Cg, Ca>::refresh(size_t newlength)
	{
		size_t i;
		vertice.refresh(newlength);
		arcs.clear();
		for (i = 0; i < vertice.count(); i++)
		{
			vertice[i].first = SizeMax;
			vertice[i].rear = SizeMax;
		}
	}
	template <class Cg, class Ca> size_t Dgraph<Cg, Ca>::FirstArc(size_t site) const
	{
		return vertice[site].first;
	}
	template <class Cg, class Ca> size_t Dgraph<Cg, Ca>::NextArc(size_t site) const
	{
		return arcs[site].next;
	}
	template <class Cg, class Ca> size_t Dgraph<Cg, Ca>::ArcTo(size_t site) const
	{
		return arcs[site].to;
	}
	template <class Cg, class Ca> size_t Dgraph<Cg, Ca>::ArcCount(size_t site) const
	{
		size_t count_, first_;
		count_ = 0;
		first_ = vertice[site].first;
		while (first_ != SizeMax)
		{
			first_ = arcs[first_].next;
			count_ += 1;
		}
		return count_;
	}
	template <class Cg, class Ca> size_t Dgraph<Cg, Ca>::append(size_t from, size_t to, const Ca& C)
	{
		size_t should;
		should = arcs.expand();
		arcs[should].from = from;
		arcs[should].to = to;
		arcs[should].content = C;
		arcs[should].next = SizeMax;
		if (vertice[from].first == SizeMax)
		{
			vertice[from].first = should;
			vertice[from].rear = should;
		}
		else
		{
			arcs[vertice[from].rear].next = should;
			vertice[from].rear = should;
		}
		return should;
	}
	template <class Cg, class Ca> void Dgraph<Cg, Ca>::append(const Dgraph<Cg, Ca>& right, size_t VerticeOffset)
	{
		size_t ArcsOffset;
		size_t i, length, temp;
		ArcsOffset = arcs.rear();
		length = right.vertice.count();
		for (i = 0; i < length; i++)
		{
			temp = (right.vertice[i].first == SizeMax ? SizeMax : right.vertice[i].first + ArcsOffset);
			vertice[i + VerticeOffset].first = temp;
			temp = (right.vertice[i].rear == SizeMax ? SizeMax : right.vertice[i].rear + ArcsOffset);
			vertice[i + VerticeOffset].rear = temp;
		}
		//begin = arcs.site();
		arcs.append(right.arcs);
		//arcs.expand(right.arcs.count());
		length = right.arcs.count();
		for (i = ArcsOffset; i < length + ArcsOffset; i++)
		{
			arcs[i].from += VerticeOffset;
			arcs[i].to += VerticeOffset;
			temp = (arcs[i].next == SizeMax ? SizeMax : arcs[i].next + ArcsOffset);
			arcs[i].next = temp;
		}
	}
	template <class Cg, class Ca> void Dgraph<Cg, Ca>::Demo(FILE* fp)const 
	{
		fprintf(fp, "vertice.count() = %llu\n", (long long int)vertice.count());
		fprintf(fp, "arcs.count() = %llu\n", (long long int)arcs.count());
		//vertice.refresh();
		//arcs.refresh();
	}

	template <class Cg> LRNFA<Cg>::LRNFA()
	{

	}
	template <class Cg> LRNFA<Cg>::~LRNFA()
	{

	}
	template <class Cg> Cg& LRNFA<Cg>::operator[](size_t target)
	{
		return vertice[target].content;
	}
	template <class Cg> const Cg& LRNFA<Cg>::operator[](size_t target) const
	{
		return vertice[target].content;
	}
	template <class Cg> void LRNFA<Cg>::refresh(void)
	{
		vertice.refresh();
		arcs.refresh();
	}
	template <class Cg> void LRNFA<Cg>::refresh(size_t newlength)
	{
		size_t i;
		vertice.refresh(newlength);
		arcs.clear();
		for (i = 0; i < vertice.count(); i++)
		{
			vertice[i].first = SizeMax;
			vertice[i].rear = SizeMax;
		}
	}
	template <class Cg> size_t LRNFA<Cg>::VortexAppend(const Cg& element)
	{
		size_t length;
		vortex V;
		length = vertice.count();
		V.first = SizeMax;
		V.rear = SizeMax;
		V.content = element;
		vertice.append(V);
		return length;
	}
	template <class Cg> size_t LRNFA<Cg>::FirstArc(size_t site) const
	{
		return vertice[site].first;
	}
	template <class Cg> size_t LRNFA<Cg>::NextArc(size_t site) const
	{
		return arcs[site].next;
	}
	template <class Cg> size_t LRNFA<Cg>::ArcTo(size_t site) const
	{
		return arcs[site].to;
	}
	template <class Cg> size_t LRNFA<Cg>::ArcCount(size_t site) const
	{
		size_t count_, first_;
		count_ = 0;
		first_ = vertice[site].first;
		while (first_ != SizeMax)
		{
			first_ = arcs[first_].next;
			count_ += 1;
		}
		return count_;
	}
	template <class Cg> size_t LRNFA<Cg>::append(size_t from, size_t to, bool Epsilon, long long int Symbol)
	{
		size_t should;
		should = arcs.expand();
		arcs[should].from = from;
		arcs[should].to = to;
		arcs[should].epsilon = Epsilon;
		arcs[should].symbol = Symbol;
		arcs[should].next = SizeMax;
		if (vertice[from].first == SizeMax)
		{
			vertice[from].first = should;
			vertice[from].rear = should;
		}
		else
		{
			arcs[vertice[from].rear].next = should;
			vertice[from].rear = should;
		}
		return should;
	}
	template <class Cg> void LRNFA<Cg>::Demo(FILE* fp) const
	{
		fprintf(fp, "vertice.count() = %llu\n", (long long int)vertice.count());
		fprintf(fp, "arcs.count() = %llu\n", (long long int)arcs.count());
		//vertice.refresh();
		//arcs.refresh();
	}
	template <class Cg> void LRNFA<Cg>::initial(bool* state, list<size_t>& stack) const
	{
		size_t i;
		state[0] = true;
		for (i = 1; i < vertice.count(); i++) state[i] = false;
		closure(state, stack);
	}
	template <class Cg> void LRNFA<Cg>::closure(bool* state, list<size_t>& stack) const
	{
		size_t delta;
		size_t Scount;
		size_t i;
		size_t now, arc, temp;
		Scount = 0;
		delta = 0;
		stack.refresh();
		for (i = 0; i < vertice.count(); i++)
			if (state[i])
			{
				Scount += 1;
				stack.append(i);
			}
		while (stack.pop(now) != 0)
		{
			arc = vertice[now].first;
			while (arc != SizeMax)
			{
				if (arcs[arc].epsilon == true)
				{
					temp = arcs[arc].to;
					if (!state[temp])
					{
						state[temp] = true;
						stack.append(temp);
						delta += 1;
					}
				}
				arc = arcs[arc].next;
			}
		}
	}
	template <class Cg> size_t LRNFA<Cg>::move(const bool* from, bool* to, long long int ele, list<size_t>& stack) const
	{
		size_t i;
		size_t Scount;
		size_t now, arc;
		Scount = 0;
		for (i = 0; i < vertice.count(); i++) to[i] = false;
		for (i = 0; i < vertice.count(); i++)
			if (from[i])
			{
				arc = vertice[i].first;
				while (arc != SizeMax)
				{
					if (arcs[arc].symbol == ele && arcs[arc].epsilon == false)
					{
						now = arcs[arc].to;
						Scount += (to[now] ? 0 : 1);
						to[now] = true;
					}
					arc = arcs[arc].next;
				}
			}
		closure(to, stack);
		return Scount;
	}
	template <class Cg> void LRNFA<Cg>::build(matlist<int>& sheet, matlist<bool>& Dstates, size_t NonTcount, size_t Tcount) const
	{
		list<size_t> stack;
		list<size_t> auxiliary;
		//matlist<bool> Dstates(graph.vertice.count());
		size_t now, old;
		bool* state;
		vec<bool> to;
		long long int ele, symbol;
		size_t Scount, TotalSymbol;
		TotalSymbol = NonTcount + Tcount;
		sheet.refresh(0, TotalSymbol, 4);
		Dstates.refresh(0, vertice.count(), 4);
		to.Malloc(vertice.count());
		auxiliary.reshape(vertice.count());
		auxiliary.refresh();
		state = Dstates.append();

		initial(state, auxiliary);
		//return;
		stack.append(0);
		sheet.append();
		//return;
		while (stack.pop(now) != 0)
		{
			//Demo(stdout, state, nfa.StateAmount);
			for (ele = 0; (size_t)ele < TotalSymbol; ele++)
			{
				state = Dstates[now];
				symbol = ele < NonTcount ? ele : -(long long int)((ele + 1) - NonTcount);
				Scount = move(state, to.vector(), symbol, auxiliary);
				//std::cout << "Scount: " << Scount << ");" << std::endl;
				if (Scount == 0) sheet[now][(size_t)ele] = -1;
				else
				{
					//std::cout << "Scount: " << Scount << ", symbol = " << symbol << std::endl;
					old = Dstates.row();
					sheet[now][(size_t)ele] = (int)(Dstates.SearchAdd(to.vector()));
					if (old != Dstates.row())
					{
						sheet.append();
						stack.append(old);
					}
					//if (old != Dstates.row()) Demo(stdout, Dstates[old], nfa.StateAmount);
				}
				//std::cout << "Scount: " << Scount << ");" << std::endl;
			}
		}
		//std::cout << "Dstates.row(): " << Dstates.row() << std::endl;
		//Demo(stdout, Dstates[old], nfa.StateAmount);
		//count = Dstates.row();
		//acceptSet(Dstates, nfa);
	}
}
namespace hyperlex
{

}
namespace hyperlex
{
	int PostfixSwitch(char c);
	bool IfHexa(char c);
	int SwitchHexa(char c);
	int SwitchOcta(char c);


	char dequeue(const char* list, size_t end, size_t& head);

	long int IntGet(const char* list, size_t end, size_t& head);
	double RealGet(int& state, const char* list, size_t end, size_t& head);
	char CharGet(const char* list, size_t end, size_t& head);

	char CharGet(int& error, const char* list, size_t end, size_t& head);
}

//#include <string>


#undef SizeMax 
#undef CharSize

#endif

/*
class StringPool
	{
	private:
		// 哈希表节点结构
		struct HashNode
		{
			char* key;// 存储字符串
			size_t id;// 唯一ID
			HashNode* next;// 指向下一个节点的指针

			HashNode(const char* k, size_t idx) {
				key = strdup(k);
				id = idx;
				next = NULL;
			}

			~HashNode() {
				free(key);
			}
		};
		//哈希表中有字符串唯一的存储副本，
		//stringArray不存储字符串的副本，而是存储指向字符串的指针。
		static const size_t INITIAL_BUCKETS = 64;// 初始桶数量
		static const double LOAD_FACTOR;// 哈希表负载因子

		// 哈希表相关成员
		HashNode** buckets;
		size_t bucketCount;// 桶数量
		size_t nodeCount;// 哈希表节点数量

		// 向量相关成员
		char** stringArray;// 存储字符串的数组
		size_t arraySize;// 数组当前大小
		size_t arrayCapacity;// 数组容量

		// 哈希函数 (djb2)
		inline size_t hash(const char* str) const
		{
			size_t hash = 5381;
			int c;
			while ((c = *str++)) {
				//hash = ((hash << 4) + hash) ^ c;//Fermat prime  17: 0.2
				hash = ((hash << 5) + hash) ^ c;//: 0.3
				//hash = ((hash << 8) + hash) ^ c;//Fermat prime 257 : 0.7
				//hash = (hash >> 16) ^ (hash & 0xFFFF); // 混合高位与低位[2,6](@ref)
				hash = (hash * 101) ^ ((hash << 5) + (hash >> 2)) ^ c;
			}
			return hash;
		}

		// 在桶中查找字符串
		inline HashNode* findInBucket(size_t index, const char* key) const
		{
			HashNode* current = buckets[index];
			while (current)
			{
				if (strcmp(current->key, key) == 0)
				{
					return current;
				}
				current = current->next;
			}
			return NULL;
		}

		// 扩展哈希表
		inline void resizeHashTable()
		{
			size_t newBucketCount = bucketCount * 2;
			HashNode** newBuckets = new HashNode * [newBucketCount]();

			for (size_t i = 0; i < bucketCount; i++)
			{
				HashNode* current = buckets[i];
				while (current) {
					HashNode* next = current->next;
					size_t newIndex = hash(current->key) % newBucketCount;

					current->next = newBuckets[newIndex];
					newBuckets[newIndex] = current;

					current = next;
				}
			}
			//std::cout << "Resizing hash table from " << bucketCount << " to " << newBucketCount << " buckets.\n";
			delete[] buckets;
			buckets = newBuckets;
			bucketCount = newBucketCount;
		}

		// 扩展数组
		inline void resizeArray()
		{
			size_t newCapacity = arrayCapacity ? arrayCapacity * 2 : 8;
			char** newArray = new char* [newCapacity];

			if (stringArray)
			{
				for (size_t i = 0; i < arraySize; i++) {
					newArray[i] = stringArray[i];
				}
				delete[] stringArray;
			}

			stringArray = newArray;
			arrayCapacity = newCapacity;
		}

	public:
		StringPool()
		{
			buckets = new HashNode * [INITIAL_BUCKETS]();
			bucketCount = INITIAL_BUCKETS;
			nodeCount = 0;

			stringArray = NULL;
			arraySize = 0;
			arrayCapacity = 0;
		}

		~StringPool() {
			// 清理哈希表
			for (size_t i = 0; i < bucketCount; i++) {
				HashNode* current = buckets[i];
				while (current) {
					HashNode* next = current->next;
					delete current;
					current = next;
				}
			}
			delete[] buckets;

			// 清理数组
			delete[] stringArray;
		}

		// 添加字符串，返回唯一ID
		inline size_t append(const char* src)
		{
			if (!src) return -1;

			size_t index = hash(src) % bucketCount;
			HashNode* node = findInBucket(index, src);
			if (node) {
				return node->id;
			}

			if (arraySize >= arrayCapacity)
			{
				resizeArray();
			}

			//char* newStr = strdup(src);
			const size_t newId = arraySize;
			arraySize++;
			//stringArray[arraySize++] = newStr;

			HashNode* newNode = new HashNode(src, newId);
			//HashNode* newNode = new HashNode(newStr, newId);
			newNode->next = buckets[index];
			buckets[index] = newNode;
			nodeCount++;

			if (static_cast<double>(nodeCount) / bucketCount > LOAD_FACTOR) {
				resizeHashTable();
			}

			stringArray[newId] = newNode->key;

			return newId;
		}

		// 根据ID获取字符串
		inline const char* getString(size_t id) const {
			if (id >= arraySize) return NULL;
			return stringArray[id];
		}

		inline const char* operator[](size_t id) const {
			return getString(id);
		}

		// 检查字符串是否存在于池中
		inline bool contains(const char* src) const {
			if (!src) return false;
			size_t index = hash(src) % bucketCount;
			return findInBucket(index, src) != NULL;
		}

		// 获取池中字符串数量
		inline size_t size() const {
			return arraySize;
		}

		// 获取哈希表元素数量
		inline size_t count() const {
			return nodeCount;
		}

		// 调试函数
		inline void demo(FILE* fp = stdout) const
		{
			fprintf(fp, "StringPool contains %zu strings:\n", arraySize);
			fprintf(fp, "LOAD FACTOR is %.6lf\n", LOAD_FACTOR);
			size_t colli = countCollisions();
			fprintf(fp, "Count of collisions %zu, collisions rate: %.6lf\n", colli, (double)colli / bucketCount);
			for (size_t i = 0; i < arraySize; i++) {
				fprintf(fp, "ID: %zu, String: %s\n", i, stringArray[i]);
			}

			for (size_t i = 0; i < arraySize; i++) {
				if (!contains(stringArray[i])) {
					fprintf(fp, "Warning: String '%s' not found in hash table!\n", stringArray[i]);
				}
			}

			if (arraySize != nodeCount) {
				fprintf(fp, "Warning: Size mismatch between vector (%zu) and hash table (%zu)!\n",
					arraySize, nodeCount);
			}
		}

		// 统计哈希冲突总数
		inline size_t countCollisions() const {
			size_t collisionCount = 0;
			for (size_t i = 0; i < bucketCount; ++i) {
				HashNode* node = buckets[i];
				if (node) {
					// 跳过桶中的首节点，只统计链表中的后续节点（冲突节点）
					node = node->next;
					while (node) {
						++collisionCount;
						node = node->next;
					}
				}
			}
			return collisionCount;
		}
		inline void copy(const StringPool& source)
		{
			// 1. 自赋值检查
			if (this == &source) return;

			// 2. 清理当前对象（避免内存泄漏）
			clear();
			for (size_t i = 0; i < source.size(); i++)
			{
				// 获取源对象中当前索引的字符串
				const char* str = source.getString(i);
				append(str);
			}

		}
		inline void append(const StringPool& source, hyperlex::vector<size_t>& NewId)
		{
			// 调整输出向量大小以匹配源对象的字符串数量
			NewId.recount(source.size());

			// 遍历源对象中的所有字符串
			for (size_t i = 0; i < source.size(); i++)
			{
				// 获取源对象中当前索引的字符串
				const char* str = source.getString(i);
				if (!str) {
					NewId[i] = static_cast<size_t>(-1); // 处理无效字符串
					//continue;
				}
				else
				{
					NewId[i] = this->append(str);
				}
				// 在当前对象中查找字符串
				//size_t bucketIndex = hash(str) % bucketCount;
				//HashNode* node = findInBucket(bucketIndex, str);

				//if (node) {
					// 字符串已存在：使用现有ID
				///	NewId[i] = node->id;
				//}
				//else {
					// 字符串不存在：添加到当前对象并获取新ID
				//	NewId[i] = this->append(str);
				//}
			}
		}
		inline void clear()
		{
			// 1. 释放哈希表
			for (size_t i = 0; i < bucketCount; ++i) {
				HashNode* current = buckets[i];
				while (current)
				{
					HashNode* next = current->next;
					delete current; // 析构HashNode（内部释放key）
					current = next;
				}
			}
			delete[] buckets;// 1.1 重新分配哈希表和字符串数组
			buckets = new HashNode * [INITIAL_BUCKETS]();
			bucketCount = INITIAL_BUCKETS;
			nodeCount = 0;

			delete[] stringArray;
			stringArray = NULL;
			arraySize = 0;
			arrayCapacity = 0;


		}
		friend void test_string_pool();
	};
*/